共查询到20条相似文献,搜索用时 15 毫秒
1.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
2.
The vertex arboricity of a graph is the minimum number of colors required to color the vertices of such that no cycle is monochromatic. The list vertex arboricity is the list-coloring version of this concept. In this note, we prove that if is a toroidal graph, then ; and if and only if contains as an induced subgraph. 相似文献
3.
For a set of vertices of a graph , a vertex in , and a vertex in , let be the distance of and in the graph . Dankelmann et al. (2009) define to be an exponential dominating set of if for every vertex in , where . Inspired by this notion, we define to be an exponential independent set of if for every vertex in , and the exponential independence number of as the maximum order of an exponential independent set of .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 for which equals the independence number for every induced subgraph of , and we give an explicit characterization of all trees with . 相似文献
4.
Chan-Wei Chang Ma-Lian Chia Cheng-Ju Hsu David Kuo Li-Ling Lai Fu-Hsing Wang 《Discrete Applied Mathematics》2012,160(4-5):479-487
Given a graph , a defensive alliance of is a set of vertices satisfying the condition that for each , at least half of the vertices in the closed neighborhood of are in . A defensive alliance is called global if every vertex in is adjacent to at least one member of the defensive alliance . The global defensive alliance number of , denoted , is the minimum size around all the global defensive alliances of . 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 -ary trees for . We also establish upper bounds and lower bounds for and , and show that the bounds are sharp for certain . 相似文献
5.
The inflation of a graph is obtained from by replacing every vertex of degree by a clique and each edge by an edge between two vertices of the corresponding cliques and of in such a way that the edges of which come from the edges of form a matching of . A set of vertices in a graph is a total dominating set, abbreviated TDS, of if every vertex of is adjacent to a vertex in . The minimum cardinality of a TDS of is the total domination number of . 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 is a connected graph of order , then , and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of to be at least , then we show that , with equality if and only if has a perfect matching. If we increase the minimum degree requirement of to be at least , then we show , with equality if and only if every minimum TDS of is a perfect total dominating set of , 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.
Christoph Brause Arnfried Kemnitz Massimiliano Marangio Anja Pruchnewski Margit Voigt 《Discrete Mathematics》2017,340(11):2633-2640
Let be a simple graph and for every vertex let be a set (list) of available colors. is called -colorable if there is a proper coloring of the vertices with for all . A function is called a choice function of and is said to be -list colorable if is -colorable for every list assignment choice function is defined by and the sum choice number
denotes the minimum size of a choice function of .Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For a generalized
-graph is a simple graph consisting of two vertices and connected by internally vertex disjoint paths of lengths
.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 and characterize all generalized -graphs which attain the trivial upper bound . 相似文献
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 is called nonintersecting if contains no crossing. For a chord diagram having a crossing , the expansion of with respect to is to replace with or . For a chord diagram , let be the chord expansion number of , which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from with a finite sequence of expansions.In this paper, it is shown that the chord expansion number equals the value of the Tutte polynomial at the point for the interlace graph corresponding to . 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 be a connected graph with vertex set and edge set . For a subset of , the Steiner distance of is the minimum size of a connected subgraph whose vertex set contains . For an integer with , the Steiner-Wiener index is . In this paper, we introduce some transformations for trees that do not increase their Steiner -Wiener index for . Using these transformations, we get a sharp lower bound on Steiner -Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well. 相似文献
19.
Let and be the domination number and the game domination number of a graph , respectively. In this paper -maximal graphs are introduced as the graphs for which holds. Large families of -maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. -maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least . 相似文献