Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

Characterizations of maximum matching graphs of certain types

The maximum matching graph of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.     

Nonorientable regular embeddings of graphs of order pq

In [J. Algeb. Combin. 19(2004), 123-141], Du et al. classified the orientable regular embeddings of connected simple graphs of order pq for any two primes p and q. In this paper, we shall classify the nonorientable regular embeddings of these graphs, where p ≠ q. Our classification depends on the classification of primitive permutation groups of degree p and degree pq but is independent of the classification of the arc-transitive graphs of order pq.     

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.     

Coedge regular graphs without 3-stars

We describe coedge regular graphs such that antineighborhoods of their vertices are coedge regular graphs with the same value of the parameterμ. As a consequence of the main theorem, we obtain a classification of coedge regular graphs without 3-stars. Translated fromMatematicheskie Zametki, Vol. 60, No. 4, pp. 495–503, October, 1996. This research was supported by the Russion Foundation for Basic Research under grants No. 93-01-01529 and No. 94-01-00802a.     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

心形图的匹配能序及Hosoya指标排序

以G(a, 4, b)(a 1, b 1)表示a+b+4个点的心形图.从匹配多项式的定义出发,通过递推关系式刻画出了这类心形图的匹配能级和它们的Hosoya指标的全排序.     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

On a family of highly regular graphs by Brouwer,Ivanov, and Klin

Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor’s non-classical $GQ(5^2,5)$, are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov’s graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are $(3,5)$-regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

A class of amply regular graphs related to the subconstituents of a dual polar graph

The connected components of the induced graphs on each subconstituent of the dual polar graph of the odd dimensional orthogonal spaces over a finite field are shown to be amply regular. The connected components of the graphs on the second and third subconstituents are shown to be distance-regular by elementary methods.     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.