共查询到20条相似文献,搜索用时 687 毫秒
1.
Keiko Kotani 《Graphs and Combinatorics》2001,17(3):511-515
Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg
G
(x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑
x
∈
V
(
G
)
f(x) is odd.
Received: June 29, 1998?Final version received: July 30, 1999 相似文献
2.
For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G. 相似文献
3.
Let G be a connected simple graph, let X?V (G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d T (x) for all x ∈ X, where d T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N G (S) ? S| ? f(S) + 2|S| ? ω G (S) ≥, where ω G (S) is the number of components of the subgraph induced by S. 相似文献
4.
Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg
F
(x)≤f(x) for all x∈V(G) and deg
F
(y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property.
Received: June 14, 1999?Final version received: August 21, 2000 相似文献
5.
The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()−1 Σ{x,y}⊂V(G) dG(x, y), where V(G) denotes the vertex set of G and dG(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K3‐free graphs, C4‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000 相似文献
6.
Haruhide Matsuda 《Discrete Mathematics》2009,309(11):3653-3658
We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σk(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σk(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σk−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that dT(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp. 相似文献
7.
An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V(G) at most f(v) times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f(G). Any simple graph G has the f-chromatic index equal to △f(G) or △f(G) + 1, where △f(G) =max v V(G){[d(v)/f(v)]}. If X′f(G) = △f(G), then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f(G) colors are given. 相似文献
8.
Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and TG(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for TG(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove TG(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show TG(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd Kn + 1‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012 相似文献
9.
A lower bound on the total signed domination numbers of graphs 总被引:4,自引:0,他引:4
Xin-zhong LU Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2007,50(8):1157-1162
Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n. 相似文献
10.
Let V be a complex vector space with basis {x
1, x
2, . . . , x
n
} and G be a finite subgroup of GL(V). The tensor algebra T(V) over the complex is isomorphic to the polynomials in the non-commutative variables x
1, x
2, . . . , x
n
with complex coefficients. We want to give a combinatorial interpretation for the decomposition of T(V) into simple G-modules. In particular, we want to study the graded space of invariants in T(V) with respect to the action of G. We give a general method for decomposing the space T(V) into simple modules in terms of words in a Cayley graph of the group G. To apply the method to a particular group, we require a homomorphism from a subalgebra of the group algebra into the character
algebra. In the case of G as the symmetric group, we give an example of this homomorphism from the descent algebra. When G is the dihedral group, we have a realization of the character algebra as a subalgebra of the group algebra. In those two
cases, we have an interpretation for the graded dimensions and the number of free generators of the algebras of invariants
in terms of those words. 相似文献
11.
Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg
G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results.
Revised: June 11, 1998 相似文献
12.
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d
H
(x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let
= {F
1, F
2, ..., F
m
} be a factorization of G and H be a subgraph of G with mr edges. If F
i
, 1 ≤i≤m, has exactly r edges in common with H, then
is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges.
This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China 相似文献
13.
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. 相似文献
14.
Let f be an integer valued function defined on the vertex set V(G) of a simple graph G. We call a subset Df of V(G) a f-dominating set of G if |N(x, G) ∩ Df| ≥ f(x) for all x ∈ V(G) — Df, where N(x, G) is the set of neighbors of x. Df is a minimum f-dominating set if G has no f-dominating set D′f with |Df| < |Df|. If j, k ∈ N0 = {0,1,2,…} with j ≤ k, then we define the integer valued function fj,k on V(G) by . By μj,k(G) we denote the cardinality of a minimum fj,k-dominating set of G. A set D ? V(G) is j-dominating if every vertex, which is not in D, is adjacent to at least j vertices of D. The j-domination number γj(G) is the minimum order of a j-dominating set in G. In this paper we shall give estimations of the new domination number μj,k(G), and with the help of these estimations we prove some new and some known upper bounds for the j-domination number. © 1993 John Wiley & Sons, Inc. 相似文献
15.
Guiying Yan 《Graphs and Combinatorics》1999,15(3):365-371
Let G be a simple graph. Let g(x) and f(x) be integer-valued functions defined on V(G) with g(x)≥2 and f(x)≥5 for all x∈V(G). It is proved that if G is an (mg+m−1, mf−m+1)-graph and H is a subgraph of G with m edges, then there exists a (g,f)-factorization of G orthogonal to H.
Received: January 19, 1996 Revised: November 11, 1996 相似文献
16.
It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σx∈V(H) degG(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999 相似文献
17.
Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C
d
n of the n-cycle C
n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C
n
d for n≡0 or (mod d+1), and lower and upper bounds for other cases.
Received: May 13, 1996 Revised: December 8, 1997 相似文献
18.
Florian Pfender 《Journal of Graph Theory》2010,64(3):206-209
For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010 相似文献
19.
F. M. Dong 《Journal of Graph Theory》2005,48(1):51-73
Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x1,x2,…,xn such that xi is contained in a K3 of G[Vi] for i = 3,4,…,n, where Vi = {x1,x2,…,xi}. This result improves two known results that μ(G) ≥ μ(On) where On is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005 相似文献
20.
Sanming Zhou 《Czechoslovak Mathematical Journal》2000,50(2):321-330
Let f be an integer-valued function defined on the vertex set V(G) of a graph G. A subset D of V(G) is an f-dominating set if each vertex x outside D is adjacent to at least f(x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by
f
(G). In a similar way one can define the connected and total f-domination numbers
c,f
(G) and
t,f
(G). If f(x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving
f
(G),
c,f
(G),
t,f
(G) and the independence domination number i(G). In particular, several known results are generalized. 相似文献