Bipartite Independent Number and Hamilton-Biconnectedness of Bipartite Graphs

Autor:	Binlong Li
Rok vydání:	2020
Předmět:	Combinatorics symbols.namesake Computer Science::Discrete Mathematics Independent set symbols Bipartite graph Discrete Mathematics and Combinatorics Hamiltonian path Theoretical Computer Science Mathematics Vertex (geometry)
Zdroj:	Graphs and Combinatorics. 36:1639-1653
ISSN:	1435-5914 0911-0119
DOI:	10.1007/s00373-020-02211-7
Popis:	Let G be a balanced bipartite graph with bipartite sets X, Y. We say that G is Hamilton-biconnected if there is a Hamilton path connecting any vertex in X and any vertex in Y. We define the bipartite independent number $$\alpha ^o_B(G)$$ to be the maximum integer $$\alpha $$ such that for any integer partition $$\alpha =s+t$$ , G has an independent set formed by s vertices in X and t vertices in Y. In this paper we show that if $$\alpha ^o_B(G)\le \delta (G)$$ then G is Hamilton-biconnected, unless G has a special construction.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3cedf44653c1dba5708703e1bef85255 https://doi.org/10.1007/s00373-020-02211-7 Zobrazit plný text záznamu Plný text ve formátu PDF