共查询到20条相似文献,搜索用时 62 毫秒
1.
A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λ c , if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In Z. Zhang, B. Wang (Super cyclically edge-connected transitive graphs, J. Combin. Optim. 22:549–562, 2011), it is proved that a connected edge-transitive graph is super-λ c if either G is cubic with girth at least 7 or G has minimum degree at least 4 and girth at least 6, and the authors also conjectured that a connected graph which is both vertex-transitive and edge-transitive is always super cyclically edge-connected. In this article, for a λ c -optimal but not super-λ c graph G, all possible λ c -superatoms of G which have non-empty intersection with other λ c -superatoms are determined. This is then used to give a complete classification of non-super-λ c edge-transitive k(k≥3)-regular graphs. 相似文献
2.
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. 相似文献
3.
Carlos J. Luz 《Journal of Combinatorial Optimization》2011,22(4):882-894
This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α
k
(G). From a well known Motzkin-Straus result, a relationship is deduced between α
k
(G) and the independence number α(G). Next, it is proved that the upper bounds υ
k
(G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ
0(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above
paper. The paper continues with the introduction of a new upper bound on α
k
(G) improving υ
k
(G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational
experiments which were performed to compare all bounds studied are reported. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
Haoli Wang Xirong Xu Yuansheng Yang Kai Lü 《Journal of Combinatorial Optimization》2011,21(4):481-496
Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k
-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k
-distance paired domination number, denoted by γ
p
k
(G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1. 相似文献
7.
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. 相似文献
8.
Mathieu Bouchard Alain Hertz Guy Desaulniers 《Journal of Combinatorial Optimization》2009,17(2):168-191
An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S
v
(G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D
v
(G,c) the minimum number of integers which must be added to S
v
(G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑
v∈V
D
v
(G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds
on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a
tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them
having a known optimal deficiency. 相似文献
9.
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). 相似文献
10.
Imagine a large building with many corridors. A robot cleans these corridors in a greedy fashion, the next corridor cleaned
is always the dirtiest to which it is incident. We determine bounds on the minimum s(G) and maximum S(G) number of time steps (over all edge weightings) before every edge of a graph G has been cleaned. We show that Eulerian graphs have a self-stabilizing property that holds for any initial edge weighting:
after the initial cleaning of all edges, all subsequent cleanings require s(G) time steps. Finally, we show the only self-stabilizing trees are a subset of the superstars. 相似文献
11.
Peter Che Bor Lam Wensong Lin Jianzhuan Wu 《Journal of Combinatorial Optimization》2007,14(2-3):219-227
Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ
j,k
-number of G, denoted by λ
j,k
(G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)|
m
≥j if u and v are adjacent; and |f(u)−f(v)|
m
≥k if u and v are at distance two apart, where |x|
m
=min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ
j,k
-number of G and denoted by σ
j,k
(G). The λ
j,k
-numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ
j,k
-numbers of direct products of two complete graphs and the σ
j,k
-numbers of direct products and Cartesian products of two complete graphs.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast
University Science Foundation grant XJ0607230. 相似文献
12.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2
e(G)⌉≤t(G)≤⌈log 2
e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that
the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite
graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or
for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or
for k≥6.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013.
G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical
Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office. 相似文献
13.
For an edge-colored graph G, we call an edge-cut M of G monochromatic if the edges of M are colored with a same color. The graph G is called monochromatically disconnected if any two distinct vertices of G are separated by a monochromatic edge-cut. The monochromatic disconnection number, denoted by md(G), of a connected graph G is the maximum number of colors that are allowed to make G monochromatically disconnected. In this paper, we solve the Erd?s-Gallai-type problems for the monochromatic disconnection, and give the monochromatic disconnection numbers for four graph products, i.e., Cartesian, strong, lexicographic, and tensor products.
相似文献14.
It is well known that if G is a multigraph then χ′(G)≥χ′*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′*(G)+c
χ′*(G) when χ′*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with
$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor
, improving the above mentioned results. As a consequence, for multigraphs G with
$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}
the answer to a 1964 problem of Vizing is in the affirmative. 相似文献
15.
Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all
vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive
the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application
of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability
of this problem and prove Ω(g1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds.
Supported in part by the NSF of China under Grant No. 70221001 and 60373012. 相似文献
16.
Suppose G is a graph of p vertices. A proper labeling
f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of
G
with respect to
f is defined by CBS
f
(G)=∑
uv∈E(G)|f(v)−f(u)|
p
, where |x|
p
=min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS
f
(G): f is a proper labeling of G}. The bandwidth sum of
G
with respect to
f is defined by BS
f
(G)=∑
uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS
f
(G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
Supported in part by the National Science Council under grants NSC91-2115-M-156-001. 相似文献
17.
Let P
G
(s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u∈P
G
(s,t)=(s,…,u,v,…,t) is defined as a shortest path P
G−e
(u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e=(u,v)∈P
G
(s,t) whose removal produces a detour at node u such that the ratio of the length of P
G−e
(u,t) to the length of P
G
(u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved
in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks
are shown.
This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under
Grant 20060401003. 相似文献
18.
Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted
version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen
these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the
set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm
for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within
a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time. 相似文献
19.
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge 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 edge-coloring of G is denoted by χ′
a
(G). Let
mad(G)\mathop{\mathrm{mad}}(G)
and Δ denote the maximum average degree and the maximum degree of a graph G, respectively. 相似文献
20.
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a??(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. In this paper, we prove that every planar graph G with girth g(G)??5 and maximum degree ????12 has a??(G)=??. 相似文献