共查询到20条相似文献,搜索用时 31 毫秒
1.
Jihui Wang Jianfeng Hou Guizhen Liu 《Journal of Applied Mathematics and Computing》2007,24(1-2):357-366
LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δf or δ f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ fc (G)=δ f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ fc (G + e) > ÷ fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ f + 1 vertices which are all δ f -vertex inG. 相似文献
2.
Mingchu Li 《Graphs and Combinatorics》1994,10(2-4):169-178
E. Schmeichel and D. Hayes showed that ifG is a 2-connected graph withd(u) +d(v)≥n ?1 for every pair of nonadjacent vertices andv, then G has a Hamiltonian cycle unlessG is the graph of Fig. 2 (b). In this paper, it is proved that, under almost the same conditions as Schmeichel and Hayes’s Theorem, namely,G is a 2-connected graph of ordern (n ≥ 40) with δ(G) ≥ 7 for every pair of nonadjacent vertices andv, G has two edge-disjoint Hamiltonian cycles unlessG is one of the graphs in Fig. 1 or Fig. 2, and this conclusion is best possible. 相似文献
3.
A graphG is called to be a 2-degree integral subgraph of aq-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactlyq- 1 triangles. An added-vertexq-treeG with n vertices is obtained by taking two verticesu, v (u, v are not adjacent) in a q-treesT withn -1 vertices such that their intersection of neighborhoods ofu, v forms a complete graphK q , and adding a new vertexx, new edgesxu, xv, xv 1,xv 2, …,xv q- 4, where {v 1,v 2,...,v q?4} ?-K q . In this paper we prove that a graphG with minimum degree not equal toq -3 and chromatic polynomialP(G;λ) = λ(λ - 1) … (λ -q +2)(λ -q +1)3(λ -q) n- q- 2 withn ≥ q + 2 has and only has 2-degree integral subgraph of q-tree withn vertices and added-vertex q-tree withn vertices. 相似文献
4.
Dr. Michael Mrva 《Monatshefte für Mathematik》1975,80(2):131-140
The graphs considered are finite and undirected, loops do not occur. An induced subgraphI of a graphX is called animitation ofX, if
- the degreesd I(v)≡d X(v) (mod 2) for allv∈V(I)
- eachu∈V(X)?V(I) is connected with the setv(I) by an even number of edges. If the set of imitations ofX consists only ofX itself, thenX is anexclusive graph. AHamiltonian graph of degree n (abbr.:HG n) in the sense ofA. Kotzig is ann-regular graph (n>1) with a linear decomposition and with the property, that any two of the linear components together form a Hamiltonian circuit of the graph.
5.
LetG be a graph and letf be a function defined on V(G) such that f(x) is a positive odd integer for everyx ? V(G). A spanning subgraphF ofG is called a [l,f]-odd factor of G if dF(x) ? {1,3,2026, f(x)} for every x ?V(G), whered F (x) denotes the degree of x inF. We discuss several conditions for a graphG to have a [1,f]-odd factor. 相似文献
6.
Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z 3-connected if and only if G is one of K 2,n?2, K 3,n?3, K 2,n?2 + , K 3,n?3 + or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240]. 相似文献
7.
Takuro Fukunaga 《Graphs and Combinatorics》2011,27(5):647-659
An undirected graph G = (V, E) is called
\mathbbZ3{\mathbb{Z}_3}-connected if for all
b: V ? \mathbbZ3{b: V \rightarrow \mathbb{Z}_3} with ?v ? Vb(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a
\mathbbZ3{\mathbb{Z}_3}-valued nowhere-zero flow
f: A? \mathbbZ3-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?e ? d+(v)f(e)-?e ? d-(v)f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are
\mathbbZ3{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the
\mathbbZ3{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs. 相似文献
8.
In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} £ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} . 相似文献
9.
Kewen Zhao 《Monatshefte für Mathematik》2009,20(1):279-293
Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and
uv \not ? E(G)}{uv \not \in E(G)\}} , and NC2(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC
2(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC
2(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC
2(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected. 相似文献
10.
Kiyoshi Yoshimoto 《Discrete Mathematics》2008,308(12):2594-2599
The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e1)+d(e2)>|V(G)|-4 for any remote edges e1,e2, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ2(G)>|V(G)|/2, then all longest cycles are dominating. 相似文献
11.
Xin Min Hou 《数学学报(英文版)》2012,28(11):2161-2168
A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al. 相似文献
12.
Shietung Peng Win-tsung Lo 《Journal of Algorithms in Cognition, Informatics and Logic》1996,20(3):445-458
Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log2n) time usingO(n) processors on an EREW PRAM model. 相似文献
13.
LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex vi ∈ V andm i the average of the degrees of the vertices adjacent to vertexv i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . 相似文献
14.
Elizabeth C.M. Maritz 《Quaestiones Mathematicae》2018,41(1):49-63
Let Π = {S1, S2, . . . , Sk} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(Cn(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators. 相似文献
15.
In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id(v). In this paper, we prove that if G is a 2-connected graph of order n such that id(u) + id(v) ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r . 相似文献
16.
Asaf Nachmias 《Geometric And Functional Analysis》2009,19(4):1171-1194
Let {G n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G n | = n. Denote by p t (v, v) the return probability after t steps of the non-backtracking random walk on G n . We show that if p t (v, v) has quasi-random properties, then critical bond-percolation on G n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G
n
} be a sequence of finite transitive graphs with vertex degree d = d(n) and |G
n
| = n. Denote by p
t
(v, v) the return probability after t steps of the non-backtracking random walk on G
n
. We show that if p
t
(v, v) has quasi-random properties, then critical bond-percolation on G
n
behaves as it would on a random graph. More precisely, if
lim sup n n1/3 ?t = 1n1/3 tpt(v,v) < ¥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,} 相似文献
17.
A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by dG(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,v∈V(G) and for each integer k with dG(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,v∈V(G), every u-v geodesic lies on every cycle of length k satisfying max{2dG(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs. 相似文献
18.
Degree conditions for group connectivity 总被引:1,自引:0,他引:1
Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K2,3,C4 and C5 by repeatedly contracting proper A-connected subgraphs, where Ck is a cycle of length k. We also show that the bound n≥13 is the best possible. 相似文献
19.
Bruce Hedman 《Journal of Combinatorial Theory, Series B》1984,37(3):270-278
A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that vivj ∈ e(G) for vi ≠ vj if and only if |f(vi) ? f(vj)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K2(G), and inductively, denote K(Km?1(G)) by Km(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kn(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived. 相似文献
20.
J. Kahn 《Israel Journal of Mathematics》2001,124(1):189-201
For given finite, connected, bipartite graphG=(V,E) with distinguishedν 0 ∈V, set {fx189-1} Our main result says there is a fixedb so that whenG is a Hamming cube ({0, 1} n with the usual adjacency), andf is chosen uniformly fromF, the probability thatf takes more thanb values is at most e?Ω(n). this settles in a very strong way a conjecture of I. Benjamini, O. Häggström and E. Mossel [2]. The proof is based on entropy considerations and a new log-concavity result. 相似文献
|