Paired-Domination in Claw-Free Cubic Graphs

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=K_1,3 or K₄–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 (K_1,3,K₄–e,C₄)-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     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

Paired-Domination Subdivision Numbers of Graphs

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.     

Upper Bounds for the Paired-Domination Numbers of Graphs

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\).     

A Characterization of Cubic Graphs with Paired-Domination Number Three-Fifths Their Order

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166–170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order.     

Paired-Domination in <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs

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 paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. In [1], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced P ₅, which seems to be the critical case.     

Subdivided trees are integral sum graphs

A graph G=(V,E) is an integral sum graph (ISG) if there exists a labeling S(G)⊂Z such that V=S(G) and for every pair of distinct vertices u,v∈V, uv is an edge if and only if u+v∈V. A vertex in a graph is called a fork if its degree is not 2. In 1998, Chen proved that every tree whose forks are at distance at least 4 from each other is an ISG. In 2004, He et al. reduced the distance to 3. In this paper we reduce the distance further to 2, i.e. we prove that every tree whose forks are at least distance 2 apart is an ISG.     

Bases for Splines on a Subdivided Domain

Let S^r() be the module of all splines of smoothness r on the rectilinear partition which subdivides some domain D. Further, let S^r() be the module of all splines of smoothness r on which also subdivides D, where is a finer subdivision of . We study the relationship between a generating set of S^r() and a generating set for S^r(). This paper gives an algorithm for extending a generating set for S^r() to one for for S^r(). This method is built on algebraic properties of splines and the Gröbner Basis Algorithm.     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

图的边韧性度

文[1]中,定义图G(V,E)的边韧性度定义为min{(|S|+T(G-S))/(ω(G-S)):S?E(G)},这里,T-(G-S)和ω(G-S)分别表示G-S中最大分支的顶点数和连通分支数.这是一个能衡量网络图稳定性较好的参数,因为它不仅考虑到了图G-S的分支数也考虑到了它的阶数.在以前的工作中,作者得到了边韧性度图的一个充要条件.利用这些结果证明了K-树是严格边韧性度图,并找到了边韧性度与较高阶的边坚韧度和边坚韧度之间的关系.     

Spatial Autocorrelation for Subdivided Populations with Invariant Migration Schemes

For populations with geographic substructure and selectively neutral genetic data, the short term dynamics is a balance between migration and genetic drift. Before fixation of any allele, the system enters into a quasi equilibrium (QE) state. Hössjer and Ryman (2012) developed a general QE methodology for computing approximations of spatial autocorrelations of allele frequencies between subpopulations, subpopulation differentiation (fixation indexes) and variance effective population sizes. In this paper we treat a class of models with translationally invariant migration and use Fourier transforms for computing these quantities. We show how the QE approach is related to other methods based on conditional kinship coefficients between subpopulations under mutation-migration-drift equilibrium. We also verify that QE autocorrelations of allele frequencies are closely related to the expected value of Moran’s autocorrelation function and treat limits of continuous spatial location (isolation by distance) and an infinite lattice of subpopulations. The theory is illustrated with several examples including island models, circular and torus stepping stone models, von Mises models, hierarchical island models and Gaussian models. It is well known that the fixation index contains information about the effective number of migrants. The spatial autocorrelations are complementary and typically reveal the type of migration (local or global).     

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

蛛网图及渔网图的邻点可区别I-全染色

通过揭示完全蛛网图和渔网图的结构特点,研究了它们的邻点可区别I-全染色问题,并运用构造法给出了其邻点可区别I-全染色,从而获得了它们的邻点可区别I-全色数.