共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
设G是一个图。G的最小度,连通度,控制数,独立控制数和独立数分别用δ,k,γ,i和α表示,图G是3-γ-临界的,如果γ=3,而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想:任意连通的3-γ临界图满足i=3,本文证明了如果G是使α=k 1≤δ的连通3-γ-临界图,那么Sumner-Blitch猜想成立。 相似文献
3.
4.
5.
设图G为简单连通图,由Vizing定理知:△(G)≤x′(G)≤△(G)+1,其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(G)=△(G),则称图G为第一类图,并简记为G∈C~1;若x′(G)=△(G)+1,则称G为第二类图,并简记为G∈C~2;A.J.W.Hilton提出了如下猜想[1]:如果G是简单图,且满足:(ⅰ)△(G)>2/3(|V(G)|-3),(ⅱ)δ(G_△)≤1。则G∈C~1。本文的目的是围绕着这一猜想,得出了两 相似文献
6.
7.
关于角格点一些猜想的证明 总被引:1,自引:1,他引:0
文 [1 ]提出了 4 5个猜想 ,但笔者没有看出其规律 ,因而不能知道被省略的猜想 ,本文将证明文 [1 ]列出的全部猜想 .首先约定 ,本文中的 A,B,C,β,γ分别表示图 1中△ ABC的三个内角及∠ PBC,∠ PCB的度数 .定理 1 在图 1中 ,cot∠ PAB =sin Csin (β γ)sin ( B C) sinγsin ( B -β)- cot( B -β) .证明 在△ ABC,△ PBC中 ,分别运用正弦定理 ,得BCsin ( B C) =ABsin C,BCsin (β γ) =PBsinγ,所以 AB =BCsin Csin ( B C) ,图 1 PB =BCsinγsin (β γ) .在△ PAB中 ,再运用正弦定理 ,得ABsin(∠ PA… 相似文献
8.
9.
10.
关于图符号的边控制 (英) 总被引:6,自引:0,他引:6
设γ's(G)和γ'ι(G)分别表示图G的符号边和局部符号边控制数,本文主要证明了:对任何n阶图G(n≥4),均有γ's(G)≤[11/6n-1]和γ'ι(G)≤2n-4成立,并提出了若干问题和猜想. 相似文献
11.
12.
A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order for each prime . 相似文献
13.
图X称为边正则图,若X的自同构群Aut(X)在X的边集上的作用是正则的.本文考察了三度边正则图与四度Cayley图的关系,给出了一个由四度Cayley图构造三度边正则图的方法,并且构造了边正则图的三个无限族. 相似文献
14.
A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups. 相似文献
15.
Brendan D. McKay 《Journal of Graph Theory》2017,85(1):7-11
A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices. 相似文献
16.
A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed. 相似文献
17.
In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs. 相似文献
18.
Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition
. Let Г
be the quotient graph of Г with respect to
. For each block B ∊
, the setwise stabiliser GB of B in G induces natural actions on B and on the neighbourhood Г
(B) of B in Г
. Let G(B) and G[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G(B) and G[B], such as the action of G[B] on B and the action of G(B) on Г
(B), and their influence on the structure of Г.
Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher
Grant from The University of Melbourne. 相似文献
19.
Alfredo García Ferran Hurtado Clemens Huemer Javier Tejel Pavel Valtr 《Computational Geometry》2009,42(9):913-922
Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. 相似文献
20.
We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W5 is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle. 相似文献