首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Let S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S?V(T). Two S-Steiner trees T1 and T2 are edge-disjoint (resp. internally vertex-disjoint) if E(T1)E(T2)=? (resp. E(T1)E(T2)=? and V(T1)V(T2)=S). Let λG(S) (resp. κG(S)) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S-Steiner trees in G, and let λk(G) (resp. κk(G)) be the minimum λG(S) (resp. κG(S)) for S ranges over all k-subset of V(G). Kriesell conjectured that if λG({x,y})2k for any x,yS, then λG(S)k. He proved that the conjecture holds for |S|=3,4. In this paper, we give a short proof of Kriesell’s Conjecture for |S|=3,4, and also show that λk(G)1k?1k?2 (resp. κk(G)1k?1k?2 ) if λ(G)? (resp. κ(G)?) in G, where k=3,4. Moreover, we also study the relation between κk(L(G)) and λk(G), where L(G) is the line graph of G.  相似文献   

2.
The vertex arboricity a(G) of a graph G is the minimum number of colors required to color the vertices of G such that no cycle is monochromatic. The list vertex arboricity al(G) is the list-coloring version of this concept. In this note, we prove that if G is a toroidal graph, then al(G)4; and al(G)=4 if and only if G contains K7 as an induced subgraph.  相似文献   

3.
For a set S of vertices of a graph G, a vertex u in V(G)?S, and a vertex v in S, let dist(G,S)(u,v) be the distance of u and v in the graph G?(S?{v}). Dankelmann et al. (2009) define S to be an exponential dominating set of G if w(G,S)(u)1 for every vertex u in V(G)?S, where w(G,S)(u)=vS12dist(G,S)(u,v)?1. Inspired by this notion, we define S to be an exponential independent set of G if w(G,S?{u})(u)<1 for every vertex u in S, and the exponential independence number αe(G) of G as the maximum order of an exponential independent set of G.Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs G for which αe(H) equals the independence number α(H) for every induced subgraph H of G, and we give an explicit characterization of all trees T with αe(T)=α(T).  相似文献   

4.
Given a graph G, a defensive alliance of G is a set of vertices S?V(G) satisfying the condition that for each vS, at least half of the vertices in the closed neighborhood of v are in S. A defensive alliance S is called global if every vertex in V(G)?S is adjacent to at least one member of the defensive alliance S. The global defensive alliance number of G, denoted γa(G), is the minimum size around all the global defensive alliances of G. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete k-ary trees for k=2,3,4. We also establish upper bounds and lower bounds for γa(Pm×Pn),γa(Cm×Pn) and γa(Cm×Cn), and show that the bounds are sharp for certain m,n.  相似文献   

5.
The inflation GI of a graph G is obtained from G by replacing every vertex x of degree d(x) by a clique X=Kd(x) and each edge xy by an edge between two vertices of the corresponding cliques X and Y of GI in such a way that the edges of GI which come from the edges of G form a matching of GI. A set S of vertices in a graph G is a total dominating set, abbreviated TDS, of G if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a TDS of G is the total domination number γt(G) of G. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if G is a connected graph of order n2, then γt(GI)2n/3, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of G to be at least 2, then we show that γt(GI)n, with equality if and only if G has a perfect matching. If we increase the minimum degree requirement of G to be at least 3, then we show γt(GI)n, with equality if and only if every minimum TDS of GI is a perfect total dominating set of GI, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.  相似文献   

6.
7.
Let G=(VE) be a simple graph and for every vertex vV let L(v) be a set (list) of available colors. G is called L-colorable if there is a proper coloring φ of the vertices with φ(v)L(v) for all vV. A function f:VN is called a choice function of G and G is said to be f-list colorable if G is L-colorable for every list assignment L choice function is defined by size(f)=vVf(v) and the sum choice number χsc(G) denotes the minimum size of a choice function of G.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For r3 a generalized θk1k2kr-graph is a simple graph consisting of two vertices v1 and v2 connected by r internally vertex disjoint paths of lengths k1,k2,,kr (k1k2?kr).In 2014, Carraher et al. determined the sum-paintability of all generalized θ-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized θ-graphs with k12 and characterize all generalized θ-graphs G which attain the trivial upper bound |V(G)|+|E(G)|.  相似文献   

8.
9.
10.
11.
A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram E is called nonintersecting if E contains no crossing. For a chord diagram E having a crossing S={x1x3,x2x4}, the expansion of E with respect to S is to replace E with E1=(E?S){x2x3,x4x1} or E2=(E?S){x1x2,x3x4}. For a chord diagram E, let f(E) be the chord expansion number of E, which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from E with a finite sequence of expansions.In this paper, it is shown that the chord expansion number f(E) equals the value of the Tutte polynomial at the point (2,?1) for the interlace graph GE corresponding to E. The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [13].  相似文献   

12.
13.
14.
15.
16.
17.
18.
Let G be a connected graph with vertex set V(G) and edge set E(G). For a subset S of V(G), the Steiner distanced(S) of S is the minimum size of a connected subgraph whose vertex set contains S. For an integer k with 2kn?1, the Steinerk-Wiener indexSWk(G) is S?V(G),|S|=kd(S). In this paper, we introduce some transformations for trees that do not increase their Steiner k-Wiener index for 2kn?1. Using these transformations, we get a sharp lower bound on Steiner k-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.  相似文献   

19.
Let γ(G) and γg(G) be the domination number and the game domination number of a graph G, respectively. In this paper γg-maximal graphs are introduced as the graphs G for which γg(G)=2γ(G)?1 holds. Large families of γg-maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. γg-maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least 3.  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号