共查询到20条相似文献,搜索用时 15 毫秒
1.
Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs. 相似文献
2.
A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted αs2(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for αs2(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for αs2(T) are established and the extremal graphs characterized. It is shown that αs2(G) can be arbitrarily large negative even for a cubic graph G. 相似文献
3.
A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009 相似文献
4.
We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K5. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K5. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K5 whose branch vertices are v and four neighbors of v. 相似文献
5.
A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
6.
A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007 相似文献
7.
A.V. Pyatkin 《Discrete Mathematics》2008,308(9):1749-1750
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. 相似文献
8.
A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs. 相似文献
9.
Bo Yu 《Journal of Graph Theory》1997,24(4):313-321
A total dominating function (TDF) of a graph G = (V, E) is a function f : V → [0, 1] such that for each v ϵ V, the sum of f values over the open neighborhood of v is at least one. Zero-one valued TDFs are precisely the characteristic functions of total dominating sets of G. We study the convexity of minimal total dominating functions. A minimal total dominating function (MTDF) f is called universal if convex combinations of f and any other MTDF are minimal. Generalizing and unifying two previous major results by Cockayne, Mynhardt and Yu in the area, we give a stronger sufficiency condition for an MTDF to be universal. Moreover, we define a splitting operation on a graph G, which preserves the universality. Using the operation, we give many more classes of graphs having a universal MTDF. © 1997 John Wiley & Sons, Inc. 相似文献
10.
Norbert Polat 《Journal of Graph Theory》1998,27(2):99-109
A ray of a graph G is isometric if every path in R is a shortest path in G. A vertex x of G geodesically dominates a subset A of V(G) if, for every finite S ⊆ V(G − x), there exists an element a of A − {x} such that the interval (set of vertices of all shortest paths) between x and a is disjoint from S. A set A ⊆ V(G) is geodesically closed if it contains all vertices which geodesically dominate A. These geodesically closed sets define a topology, called the geodesic topology, on V(G). We prove that a connected graph G has no isometric rays if and only if the set V(G) endowed with the geodesic topology is compact, or equivalently if and only if the vertex set of every ray in G is geodesically dominated. We prove different invariant subgraph properties for graphs containing no isometric rays. In particular we show that every self-contraction (map which preserves or contracts the edges) of a chordal graph G stabilizes a non-empty finite simplex (complete graph) if and only if G is connected and contains no isometric rays and no infinite simplices. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 99–109, 1998 相似文献
11.
A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least
one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination
and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph
in terms of the signed domination number of the graph. 相似文献
12.
A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)?f(v) for every v∈V(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds. 相似文献
13.
Adam Berliner Ulrike Bostelmann Richard A. Brualdi Louis Deaett 《Graphs and Combinatorics》2006,22(2):173-183
Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs Kn are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum
choice greedy is also sum choice greedy. We also determine the sum choice number of K2,n, and we show that every tree on n vertices can be obtained from Kn by consecutively deleting single edges where all intermediate graphs are sc-greedy. 相似文献
14.
A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A dk-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, dT(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a dk-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998 相似文献
15.
Peter Weidl 《Journal of Graph Theory》1995,20(1):101-112
Let v be an arbitrary vertex of a 4-edge-connected Eulerian graph G. First we show the existence of a nonseparating cycle decompositiion of G with respect to v. With the help of this decomposition we are then able to construct 4 edge-independent spanning trees with the common root v in the sam graph. We conclude that an Eulerian graph G is 4-edge-connected iff for every vertex r ? V (G) there exist 4 edge-independent spanning trees with a common root r. © 1996 John Wiley & Sons, Inc. 相似文献
16.
A graph G = (V, E) is said to be weakly four‐connected if G is 4‐edge‐connected and G – x is 2‐edge‐connected for every x ∈ V. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of a conjecture of A. Frank . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 230–242, 2006 相似文献
17.
Hong‐Jian Lai 《Journal of Graph Theory》2003,42(3):211-219
Let G be a graph. For each vertex v ∈V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), Nv is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003 相似文献
18.
A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006 相似文献
19.
Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑v∈Vf(v). The Roman domination number of a graph G, denoted by γR(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γR(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22]. 相似文献
20.
Kazuhide Hirohata 《Journal of Graph Theory》1998,29(3):177-184
For a graph G and an integer k ≥ 1, let ςk(G) = dG(vi): {v1, …, vk} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς2(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998 相似文献