距离正则图的推广

本文研究了直径为d(Γ) ≥ 2的距离正则图Γ的补图.利用Γ的交叉数分别证明了当d=2时,Γ的补图式强正则;当d ≥ 3时,Γ的补图是广义强正则.将文献[2]中的距离正则图Grassmann图、对偶极图、Hamming图推广到它们的补图,从而得到广义强正则图.     

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.     

正则图的变换图的谱

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

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.     

简单完整正则平面图

对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 .     

Regular induced subgraphs of a random Graph

An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

Classifying cubic symmetric graphs of order 10p or 10p~2

A graph is called s-regular if its automorphism group acts regularly on the set of its s-arcs. In this paper, the s-regular cyclic or elementary abelian coverings of the Petersen graph for each s ≥ 1 are classified when the fibre-preserving automorphism groups act arc-transitively. As an application of these results, all s-regular cubic graphs of order 10p or 10p2 are also classified for each s ≥ 1 and each prime p, of which the proof depends on the classification of finite simple groups.     

On the Monotonicity of (κ; g, h)-graphs

A (k;g)-graph is a k-regular graph with girth g. A (k;g)-cage is a (k;g)-graph with the least possible number of vertices. Let f(k;g) denote the number of vertices in a (k;g)-cage. The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. A fc-regular graph with girth pair (g,h) is called a (k;g,h)-graph. A (k;g,h)-cage is a (k;g,h)-graph with the least possible number of vertices. Let f(k;g,h) denote the number of vertices in a (k;g,h)-cage. In this paper, we prove the following strict inequality f(k;h-1,h)相似文献   

Clique-transversal sets in 4-regular claw-free 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 by τ _c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.     

2n-正则简单图的边连通度

图的各种连通度概念被先后用来研究网络可靠性问题.对于0到2n之间的任意一个偶数2m,构造了一个2n-正则简单图,使得其边连通度的值为2m.从而得到:2n-正则简单图的边连通度能够取{0,2,4,…,2n}中的任何一个偶数.     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009