共查询到19条相似文献,搜索用时 78 毫秒
1.
通过对子图和围长的研究,完全刻画了直径为3的3-正则简单平面图,获得了这类图仅有的11个非同构图. 相似文献
2.
我们知道当图的顶点数n>12时不存在正则极大平面图.相关文献提出了(k,l)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.在相关文献中,作者分别讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法.本文讨论了阶n(≤12)的(k,l)-正则极大平面图的存在性,除两种情况外,本文给出了阶n(≤12)的(k,l)-正则极大平面图的存在条件及其一种构造的例子. 相似文献
3.
这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面图,仍然是NP-完全的。而且,此结果是最好的可能。 相似文献
4.
5.
盛集明 《数学的实践与认识》2010,40(1)
图的各种连通度概念被先后用来研究网络可靠性问题.对于0到2n之间的任意一个偶数2m,构造了一个2n-正则简单图,使得其边连通度的值为2m.从而得到:2n-正则简单图的边连通度能够取{0,2,4,…,2n}中的任何一个偶数. 相似文献
6.
7.
8.
1988年,张忠输等证明了对于△(G)≥3的外平面图G,全色数XT(G)=△(G)+1.本文给出此结论一个简单证明,方法是全新的. 相似文献
9.
全无赘数irt是图的一个重要参数.本文对irt=0的正则图的结构进行了探讨,提供了构造irt=0的正则图的一个方法. 相似文献
10.
这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面力,仍然是NP-完全的,而且,此结果是最好的可能。 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
This paper characterizes directed graphs which are Cayley graphs of strong semilattices of groups and, in particular, strong chains of groups, i.e. of completely regular semigroups which are also called Clifford semigroups. 相似文献
14.
Strongly Regular Decompositions of the Complete Graph 总被引:3,自引:0,他引:3
Edwin R. van Dam 《Journal of Algebraic Combinatorics》2003,17(2):181-201
We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic. 相似文献
15.
《Journal of Graph Theory》2018,88(4):631-640
The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs. 相似文献
16.
Anna Kasikova 《Journal of Algebraic Combinatorics》1997,6(3):247-252
In [3] Cameron et al. classified strongly regular graphs with strongly regular subconstituents. Here we prove a theorem which implies that distance-regular graphs with strongly regular subconstituents are precisely the Taylor graphs and graphs with a
1 = 0 and a
i {0,1} for i = 2,...,d. 相似文献
18.
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. 相似文献
19.
In this note, we give a construction of strongly regular Cayley graphs. The presented construction is based on choosing cyclotomic classes in finite fields, and our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White [B. Schmidt, C. White, All two-weight irreducible cyclic codes, Finite Fields Appl. 8 (2002), 321–367] into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums. 相似文献