共查询到20条相似文献,搜索用时 31 毫秒
1.
Vertex and Tree Arboricities of Graphs 总被引:1,自引:0,他引:1
This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs. 相似文献
2.
Paul Dorbec Michael A. Henning Douglas F. Rall 《Journal of Combinatorial Optimization》2008,16(1):68-80
In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning,
M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ
t
(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ
t
(G)Γ
t
(H)≤2Γ
t
(G □ H).
Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
3.
Yuan-Zhen Huang Chun-Ying Chiang Liang-Hao Huang Hong-Gwa Yeh 《Journal of Combinatorial Optimization》2012,24(3):266-279
A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that ??close?? transmitters must receive different channels and ??very close?? transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2,1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0,1,2,??,k} such that |f(x)?f(y)|??2 if d(x,y)=1 and $f(x)\not =f(y)$ if d(x,y)=2, where d(x,y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2,1)-labeling, denoted by ??(G), is called the ??-number of G. Very little is known about ??-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n??3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that ??(G)??7 for all generalized Petersen graphs G of order n??7. Later, Adams, Cass and Troxell proved that Georges and Mauro??s conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro??s conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12. 相似文献
4.
We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G). 相似文献
5.
An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for
an adjacent vertex distinguishing total coloring of G is denoted by χ″
a
(G). In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs. 相似文献
6.
Paul Dorbec Sylvain Gravier Michael A. Henning 《Journal of Combinatorial Optimization》2007,14(1):1-7
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206).
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. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs. 相似文献
7.
Let γ
t
{k}(G) denote the total {k}-domination number of graph G, and let
denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices,
. As a corollary of this result, we have
for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005).
The work was supported by NNSF of China (No. 10701068 and No. 10671191). 相似文献
8.
Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum
cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math.
155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs.
In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs. 相似文献
9.
On backbone coloring of graphs 总被引:1,自引:0,他引:1
Weifan Wang Yuehua Bu Micka?l Montassier André Raspaud 《Journal of Combinatorial Optimization》2012,23(1):79-93
Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum
average degree, graphs with maximum degree 3, etc. 相似文献
10.
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 maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized. 相似文献
11.
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ
r
(G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show
that if G is a cubic graph of order n, then
gr(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4}
, and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then
gr(G) £ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}.
Lastly, we show that if G is a claw-free cubic graph, then γ
r
(G)=γ(G). 相似文献
12.
A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ
tr
(G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ
tr
(G)=n. Also, we show that γ
tr
(G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound. 相似文献
13.
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩S≠N[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating
set. 相似文献
14.
O. Favaron H. Karami R. Khoeilar S. M. Sheikholeslami 《Journal of Combinatorial Optimization》2010,20(1):76-84
A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number
γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number
sdgt(G)\mathrm {sd}_{\gamma_{t}}(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 total domination number. In this paper we prove that
sdgt(G) £ gt(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1
for some classes of graphs. 相似文献
15.
Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ kp (G). In this paper, we give characterizations of graphs for which γ kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees. 相似文献
16.
Hans L. Bodlaender 《Journal of Combinatorial Optimization》2003,7(3):283-290
A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth. 相似文献
17.
On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs 总被引:1,自引:1,他引:0
Weiping Shang Frances Yao Pengjun Wan Xiaodong Hu 《Journal of Combinatorial Optimization》2008,16(2):99-106
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation
algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.
This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural
Science Foundation of China under Grant No. 70221001, 10531070 and 10771209. 相似文献
18.
A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ toc (G) is the minimum size of such a set. We give some properties and bounds for γ toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs. 相似文献
19.
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. We characterize the set of vertices of a tree that are contained in all, or in no, minimum paired-dominating
sets of the tree.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
20.
The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely
related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored
by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ
p
(G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds
for such graphs and exact results for a subfamily of generalized Petersen graphs. 相似文献