On the connectivity of bipartite distance-balanced graphs

A connected graph Γ is said to be distance-balanced whenever for any pair of adjacent vertices u,v of Γ the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In [K. Handa, Bipartite graphs with balanced (a,b)-partitions, Ars Combin.51 (1999), 113-119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the negative. Moreover, we show that a minimal bipartite distance-balanced graph, that is not a cycle and is not 3-connected, has 18 vertices and is unique. In addition, we give a complete classification of non-3-connected bipartite distance-balanced graphs for which the minimal distance between two vertices in a 2-cut is three. All such graphs are regular and for each k≥3 there exists an infinite family of such graphs which are k-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs.     

Almost all regular graphs are hamiltonian

In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ? 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ? 3. © 1994 John Wiley & Sons, Inc.     

Generating random regular graphs

An algorithm is described which generates a random labeled cubic graph on n vertices. Also described is a procedure which, if successful, generates a random (0,1)-matrix with prescribed row and column sums. The latter yields procedures which, if successful, generate random labeled graphs with specified degree sequence and random labeled bipartite graphs with specified degree sequences. These procedures can be implemented so that each trial requires time which is linear in the number of vertices plus edges, but in generating a random r-regular graph, the probability of success of a given trial is about $\text{exp}\text{(}\text{(1 ? r}{}^2\text{)}\text{4}\text{)}$, which is prohibitively small for large r. Comparisons are made between the complexities of the two methods of generating random cubic graphs. The two general schemes presented derive from methods which have been used to enumerate regular graphs, both asymptotically and exactly.     

The least eigenvalue of a graph with cut vertices

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound.     

Computation of best possible low degree expanders

We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs.     

s-REGULAR DIHEDRAL COVERINGS OF THE COMPLETE GRAPH OF ORDER 4

§1. Introduction For a ?nite, simple, and undirected graph X, every edge of X gives rise to a pair ofopposite arcs, and we denote by V (X), E(X), A(X) and Aut(X) the vertex set, the edgeset, the arc set and the automorphism group of X, respectively. …     

Maximum k-colorable subgraphs

A lower bound is established on the number of edges in a maximum k-colorable subgraph of a loopless graph G. For the special case of 3-regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Eigenvalues and expansion of bipartite graphs

We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of connected bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes of graphs that are optimal with respect to the bounds. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c, d)-regular bipartite graphs and compare that with with a classical bound.     

Zero forcing sets and bipartite circulants

In this paper we introduce a class of regular bipartite graphs whose biadjacency matrices are circulant matrices – a generalization of circulant graphs which happen to be bipartite – and we describe some of their properties. Notably, we compute upper and lower bounds for the zero forcing number for such a graph based only on the parameters that describe its biadjacency matrix. The main results of the paper characterize the bipartite circulant graphs that achieve equality in the lower bound and compute their minimum ranks.     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.     

Some Combinatorial Aspects of Constructing Bipartite-Graph Codes

We propose geometrical methods for constructing square 01-matrices with the same number n of units in every row and column, and such that any two rows of the matrix contain at most one unit in common. These matrices are equivalent to n-regular bipartite graphs without 4-cycles, and therefore can be used for the construction of efficient bipartite-graph codes such that both the classes of its vertices are associated with local constraints. We significantly extend the region of parameters m, n for which there exist an n-regular bipartite graph with 2m vertices and without 4-cycles. In that way we essentially increase the region of lengths and rates of the corresponding bipartite-graph codes. Many new matrices are either circulant or consist of circulant submatrices: this provides code parity-check matrices consisting of circulant submatrices, and hence quasi-cyclic bipartite-graph codes with simple implementation.     

Resistance dimension,random walk dimension and fractal dimension

In this paper, we generalize a theorem due to Telcs concerning random walks on infinite graphs, which describes the relation of random walk dimension, fractal dimension and resistance dimension. Moreover, we obtain a reasonable upper bound and lower bound on the hitting time in terms of resistance for some nice graphs. In fact, the conditions given in this paper are weaker than those obtained by A. Telcs.Partly supported by National Natural Science Foundation and State Educational Committee of China.     

The non-existence of certain regular graphs of girth 5

For certain positive integers k it is shown that there is no k-regular graph with girth 5 having k² + 3 vertices. This provides a new lower bound for the number of vertices of girth 5 graphs with these valences.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis. Received: February 6, 1998