共查询到20条相似文献,搜索用时 562 毫秒
1.
2.
3.
5.
6.
Felix Goldberg 《Linear and Multilinear Algebra》2013,61(6):437-451
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. 相似文献
7.
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. 相似文献
8.
Michael Krivelevich Benny Sudakov Nicholas Wormald 《Random Structures and Algorithms》2011,38(3):235-250
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 相似文献
9.
On the noncommuting graph associated with a finite group 总被引:6,自引:0,他引:6
10.
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. 相似文献
11.
12.
冯纪先 《数学的实践与认识》2005,35(1):106-111
对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 . 相似文献
13.
Classifying cubic symmetric graphs of order 10p or 10p~2 总被引:1,自引:0,他引:1
KWAK Jin Ho 《中国科学A辑(英文版)》2006,49(3)
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. 相似文献
14.
盛集明 《数学的实践与认识》2010,40(1)
图的各种连通度概念被先后用来研究网络可靠性问题.对于0到2n之间的任意一个偶数2m,构造了一个2n-正则简单图,使得其边连通度的值为2m.从而得到:2n-正则简单图的边连通度能够取{0,2,4,…,2n}中的任何一个偶数. 相似文献
15.
16.
《Discrete Mathematics》2019,342(10):2818-2820
17.
Bao-guang Xu Ping Wang Jian-fang WangInstitute of Policy Management Chinese Academy of Sciences Beijing ChinaDepartment of Mathematics Statistics Computer Science St. Francis Xavier University Antigonish NS Canada BG WInstitute of Applied Mathematics Academy of Mathematics System Sciences Chinese Academy of Sciences Beijing China 《应用数学学报(英文版)》2002,(3)
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)相似文献
18.
A regular edge-transitive graph is said to be semisymmetric if it is not vertex-transitive.By Folkman [J.Combin.Theory 3(1967),215-232],there is no semisymmetric graph of order 2p or 2p 2 for a prime p,and by Malni et al.[Discrete Math.274(2004),187-198],there exists a unique cubic semisymmetric graph of order 2p 3,the so called Gray graph of order 54.In this paper,it is shown that there is no connected cubic semisymmetric graph of order 4p 3 and that there exists a unique cubic semisymmetric graph of orde... 相似文献
19.
J. Díaz A. C. Kaporis G. D. Kemkes L. M. Kirousis X. Pérez N. Wormald 《Journal of Graph Theory》2009,61(3):157-191
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 相似文献
20.
Feng-Gao Li 《Discrete Mathematics》2006,306(22):2909-2915
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. 相似文献