Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

Hamiltonian and long paths in bipartite graphs with connectivity

Let G be a graph, $\nu (G)$ the order of G, $\kappa (G)$ the connectivity of G and k a positive integer such that $k\le (\nu (G)?2)/2$. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets $V_1$ and $V_2$ is defined to be Hamiltonian-laceable if such that $|V_1|=|V_2|$ and for every pair of vertices $p\in V_1$ and $q\in V_2$, there exists a Hamiltonian path in G with endpoints p and q, or $|V_1|=|V_2|+1$ and for every pair of vertices $p,q\in V_1,p\ne q$, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition $(X,Y)$. Define $bn(G)$ to be a maximum integer such that $0\le bn(G)<min\{|X|,|Y|\}$ and (1) for each non-empty subset S of X, if $|S|\le |X|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|X|?bn(G)<|S|\le |X|$, then $N(S)=Y$; and (2) for each non-empty subset S of Y, if $|S|\le |Y|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|Y|?bn(G)<|S|\le |Y|$, then $N(S)=X$; and (3) $bn(G)=0$ if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|$ and $bn(G)>0$. In this paper, we show that if $\nu (G)\le 2\kappa (G)+4bn(G)?4$, then G is Hamiltonian-laceable; or if $\nu (G)>6bn(G)?2$, then for every pair of vertices $x\in X$ and $y\in Y$, there is an $(x,y)$-path P in G with $|V(P)|\ge 6bn(G)?2$. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.     

Longest paths and cycles in bipartite oriented graphs

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2), on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

On the construction of cospectral nonisomorphic bipartite graphs

In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using the notion of partitioned tensor products. This extends the construction of Ji, Gong, and Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction [4], and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al.     

A note on internally disjoint alternating paths in bipartite graphs

Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let x∈X and y∈Y. Let k be a positive integer. Then we prove that if G has k internally disjoint alternating paths between x and y with respect to some perfect matching, then G has k internally disjoint alternating paths between x and y with respect to every perfect matching.     

A generalized construction of chromatic index critical graphs from bipartite graphs

We prove that any graph with maximum degree n which can be obtained by removing exactly 2n - 1 edges from the join K¹ + K^{n, n} is n-critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to Yap.     

Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs

It is proved that for every positive integers k, r and s there exists an integer n = n(k,r,s) such that every k‐connected graph of order at least n contains either an induced path of length s or a subdivision of the complete bipartite graph K_k,r. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 270–274, 2004     

On connectivities of tree graphs

Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.     

On the connectivities of finite and infinite graphs

Results byW. Mader and the authors on the connectivity of finite graphs are generalized to include infinite graphs. In the infinite case a distinction must be made concerning the distribution of finite and infinite components with respect to the separating sets. Results are obtained relating these components to the atoms.     

The connectivities of adjacent tree graphs

The connectivity and the circuit rank of a graphG are denoted byx(G) and, respectively. It is shown that ifH is the adjacent tree graph of a simple connected graphG, thenx(H)=2.     

The connectivities of line and total graphs

Sharp lower bounds for the point connectivity and line connectivity of the line graph L(G) and the total graph T(G) of a graph G are determined. The lower bounds are expressed in terms of the point connectivity k, line connectivity λ, and minimum degree δ of G. It is also shown that 2λ is an upper bound for k(T(G)) and that λ(T(G))= 2δ = δ(T(G)). In each case the realizable values beyond the lower bound are determined.     

Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009