共查询到20条相似文献,搜索用时 15 毫秒
1.
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by pr(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F=K1,3 or K4–e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K1,3,K4–e,C4)-free, then pr(G)3n/8; (ii) if G is claw-free and diamond-free, then pr(G)2n/5; (iii) if G is claw-free, then pr(G)n/2. In all three cases, the extremal graphs are characterized.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. This paper was written while the second author was visiting the Laboratoire de Recherche en Informatique (LRI) at the Université de Paris-Sud in July 2002. The second author thanks the LRI for their warm hospitality 相似文献
2.
3.
The b-chromatic number of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex adjacent to some vertex in all the other color classes.
It is proved that with four exceptions, the b-chromatic number of cubic graphs is 4. The exceptions are the Petersen graph,
K
3,3, the prism over K
3, and one more sporadic example on 10 vertices. 相似文献
4.
王春香 《数学物理学报(A辑)》2009,29(1):145-150
如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K4) 且不含诱导子图K4-e, 则 β(G) =n/3. 相似文献
5.
6.
7.
A paired-dominating set of a graph G = (V, E) with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ
pr
(G), is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number
sd
γpr
(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. In this paper we establish upper bounds
on the paired-domination subdivision number and pose some problems and conjectures. 相似文献
8.
It is proved that the Cartesian product of an odd cycle with the complete graph on 2 vertices, is determined by the spectrum of the adjacency matrix. We also present some computational results on the spectral characterization of cubic graphs on at most 20 vertices. 相似文献
9.
一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.本文证明了一个2p~2(p为素数)阶连通3度点传递图或者是Calyley图,或者同构于广义Petersen图P(p~2,t),这里t~2≡-1(modp~2). 相似文献
10.
Acta Mathematicae Applicatae Sinica, English Series - A regular edge-transitive graph is said to be semisymmetric if it is not vertex-transitive. Let p be a prime. By Folkman [J. Combin. Theory 3... 相似文献
11.
12.
A graph X is said to be G-semisymmetric if it is regular and there exists a subgroup G of A := Aut (X) acting transitively on its edge set but not on its vertex set. In the case of G = A, we call X a semisymmetric graph. Let p be a prime. It was shown by Folkman (J Comb Theory 3:215–232, 1967) that a regular edge-transitive graph of order 2p or 2p 2 is necessarily vertex-transitive. The smallest semisymmetric graph is the Folkman graph. In this study, we classify all connected cubic semisymmetric graphs of order 18p n , where p is a prime and \({n \geq 1}\) . 相似文献
13.
设G为一个P阶图,γ(G)表示G的控制数.显然γ(G)≤[p/2].本文的目的是刻画达到这个上界的连通图.主要结果:(1)当p为偶数时,γ(G)=p/2当且仅当G≈C4或者G为某连通图的冠;(2)当p为奇数时,γ(G)=(p-1)/2当且仅当G的每棵生成树为定理3.1中所示的两类树之一. 相似文献
14.
成会文 《数学的实践与认识》2011,41(4)
群G的Cayley图Cay(G,S)称为是正规的,如果G的右正则表示R(G)在Cay(G,S)的全自同构群中正规.设p为奇素数,相关文献决定了4p阶连通3度Cayley图的正规性.本文给出了上述文献的主要结果的一个新的简短的证明. 相似文献
15.
A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\). 相似文献
16.
17.
A classification of connected vertex‐transitive cubic graphs of square‐free order is provided. It is shown that such graphs are well‐characterized metacirculants (including dihedrants, generalized Petersen graphs, Möbius bands), or Tutte's 8‐cage, or graphs arisen from simple groups PSL(2, p). 相似文献
18.
In a classical 1986 paper by Erdös, Saks and Saós every graph of radius r has an induced path of order at least 2r ? 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well. 相似文献
19.
20.
Oleg Pikhurko 《Graphs and Combinatorics》2007,23(6):681-689
A graph G is product anti-magic if one can bijectively label its edges with integers 1, . . . ,e(G) so that no two vertices have the same product of incident labels. This property was introduced by Figueroa-Centeno, Ichishima,
and Muntaner-Batle who in particular conjectured that every connected graph with at least 4 vertices is product anti-magic.
Here, we completely describe all product anti-magic graphs of sufficiently large order, confirming the above conjecture in
this case. Our proof uses probabilistic methods.
Reverts to public domain 28 years from publication.
Partially supported by the National Science Foundation, Grant DMS-0457512. 相似文献