Bipartite Independent Number and Hamilton-Biconnectedness of Bipartite Graphs
- PDF / 511,070 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 288 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Bipartite Independent Number and HamiltonBiconnectedness of Bipartite Graphs Binlong Li1,2 Received: 14 February 2019 / Revised: 19 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract 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 aoB ðGÞ to be the maximum integer a such that for any integer partition a ¼ 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 aoB ðGÞ dðGÞ then G is Hamilton-biconnected, unless G has a special construction. Keywords Balanced bipartite graph Bipartite independent number Hamiltonicity Hamilton-biconnectedness
1 Introduction A graph G is traceable if G has a Hamilton path, i.e., a path containing all vertices of G; G is Hamiltonian if G has a Hamilton cycle, i.e., a cycle containing all vertices of G; and G is Hamilton-connected if for each two distinct vertices u; v 2 VðGÞ, G has a Hamilton (u, v)-path, i.e., a Hamilton path connecting u and v. The Hamilton problem is a widely studied field in graph theory. For terminology and a survey we refer the reader to [10]. Supported by NSFC (11601429) and the Fundamental Research Funds for the Central Universities (3102019ghjd003). & Binlong Li [email protected] 1
Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an 710129, People’s Republic of China
2
Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an 710129, People’s Republic of China
123
Graphs and Combinatorics
As usual, we denoted by G(X, Y) a bipartite graph with bipartite sets X, Y, i.e., a graph such that every edge has one vertex in X and the other in Y. Clearly a bipartite graph (apart from K2 ) cannot be Hamilton-connected; and a bipartite graph is Hamiltonian only if it is balanced, i.e., the two bipartite sets X, Y have the same size. Let G ¼ GðX; YÞ be a balanced bipartite graph. If for every two vertices x 2 X and y 2 Y, G has a Hamilton (x, y)-path, then we say that G is Hamiltonbiconnected. This concept was introduced by Simmons [15] (where it is called Hamilton-laceable in [15]). See [1, 16, 17] for some research on the field. Note that every Hamilton-biconnected balanced bipartite graph (apart from K2 ) is Hamiltonian. A classical condition for Haniltonian property of graphs is Chva´tal–Erd} os’ condition concerning independent number and connectivity of graphs. Let mðGÞ, aðGÞ, dðGÞ and jðGÞ denote the order, the independent number, the minimum degree, and the connectivity of G, respectively. Theorem 1 (Chva´tal, Erd} os [5]) Let G be a graph of order at least three. If aðGÞ jðGÞ, then G is Hamiltonian; if aðGÞ jðGÞ 1, then G is Hamiltonconnected. Note that every bipartite graph has independent number at least half of its order. It is not interesting to apply Chva´tal–Erd
Data Loading...
