首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 593 毫秒
1.
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.  相似文献   

2.
If G is a connected graph having no vertices of degree 2 and L(G) is its line graph, two results are proven: if there exist distinct edges e and f with L(G) ? e ? L(G) ? f then there is an automorphism of L(G) mapping e to f; if G ? u ¦ G ? v for any distinct vertices u, v, then L(G) ? e ¦ L(G) ? f for any distinct edges e, f.  相似文献   

3.
Let G be a graph, A(G) its adjacency matrix. We prove that, if the least eigenvalue of A(G) exceeds -1 ? √2 and every vertex of G has large valence, then the least eigenvalue is at least -2 and G is a generalized line graph.  相似文献   

4.
With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph Lm(G) of G is defined to be L(Lm-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ np ? 3, if the removal of any k vertices, 0 ≤ kn, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L2(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L2(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that Lm(G) is n-Hamiltonian for every mk is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.  相似文献   

5.
Let G be a graph. The core of G, denoted by G Δ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) denotes the maximum degree of G. A k -edge coloring of G is a function f : E(G) → L such that |L| = k and f (e 1) ≠ f (e 2) for all two adjacent edges e 1 and e 2 of G. The chromatic index of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G) = Δ(G) and Class 2 if χ′(G) = Δ(G) + 1. In this paper it is shown that every connected graph G of even order whose core is a cycle of order at most 13 is Class 1.  相似文献   

6.
A graph G is edge-L-colorable, if for a given edge assignment L={L(e):eE(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all eE(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for eE(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.  相似文献   

7.
A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let Ne(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uvE(G), if xNe(u) and yNe(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].  相似文献   

8.
Connectivity of iterated line graphs   总被引:1,自引:0,他引:1  
Let k≥0 be an integer and Lk(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L2(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L2(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.  相似文献   

9.
A 2‐connected graph G is a critical block if G ? v is not 2‐connected for every vertex vV(G). A critical block G is a saturated critical block if G + e is not a critical block for any new edge e. The structure of all saturated critical blocks and a procedure for constructing every saturated critical block are determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 223–237, 2003  相似文献   

10.
1IntroductionInthispaperweshallconsideronlyundirected2-connectedsimplegraphs,i.e,graphsthatareloopless,finite,undirectedandwithoutmultipleedges.AgraphGissaidtobegeodeticifanypairofpointsofGarejoinedbyauniquepathofshortestlength,i.e,aulliquedistancepath[1].A2-connectedgeodeticgraphiscalledageodeticblock.Agrapllisgeodeticiffeachofitsblocksisgeodetic(seeStempleandWatkins['l).Obviously,oddcycle,tree,completegrapharegeodeticgraph,wecallthemthetrivialgeodeticgraph.Nowweonlycollsidertilenontrivial…  相似文献   

11.
The concept of a k-sequential graph is presented as follows. A graph G with ∣V(G)∪ E(G)∣=t is called k-sequential if there is a bijection?: V(G)∪E(G) → {k,k+1,…,t+k?1} such that for each edgee?=xyin E(G) one has?(e?) = ∣?(x)??(y)∣. A graph that is 1-sequential is called simply sequential, and, in particular the author has conjectured that all trees are simply sequential. In this paper an introductory study of k-sequential graphs is made. Further, several variations on the problems of gracefully or sequentially numbering the elements of a graph are discussed.  相似文献   

12.
Let G be a graph. We denote p(G) and c(G) the order of a longest path and the order of a longest cycle of G, respectively. Let κ(G) be the connectivity of G, and let σ 3(G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p(G) ? c(G) ≥ 2, then either (i) c(G) ≥ σ 3(G) ? 3 or (ii) κ(G)?=?2 and p(G) ≥ σ 3(G) ? 1. This result implies several known results as corollaries and gives a new lower bound of the circumference.  相似文献   

13.
A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e and e in E(G), G has a spanning (e,e)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any XE(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that XE(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.  相似文献   

14.
A simple graph G(X, E) is factor-critical if the induced subgraph 〈Xx〉 admits a perfect matching for every vertex x of G. It is equimatchable if every maximal matching of G is maximum. The equimatchable non-factor-critical graphs have been studied by Lesk, Plummer, and Pulleyblank. In this paper, we study the equimatchable factor-critical graphs; in particular we show that if such a graph is two-connected, it is hamiltonian.  相似文献   

15.
A set of vertices S is said to dominate the graph G if for each v ? S, there is a vertex uS with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, uV(G) with v not adjacent to u, γ(G + vu) < γ(G). Thus G is k-y-critical if γ(G) = k and for each edge e ? E(G), γ(G + e) = k ?1. The 2-domination critical graphs are characterized the properties of the k-critical graphs with k ≥ 3 are studied. In particular, the connected 3-critical graphs of even order are shown to have a 1-factor and some stringent restrictions on their degree sequences and diameters are obtained.  相似文献   

16.
A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge eE(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge eE(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xyE(G) with xX and yY. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.  相似文献   

17.
A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k*-container if it contains all vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. The spanning connectivity of G, κ*(G), is defined to be the largest integer k such that G is w*-connected for all 1?w?k if G is a 1*-connected graph. In this paper, we prove that κ*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.  相似文献   

18.
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 vivje(G) for vivj 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.  相似文献   

19.
Let ?(G) be theclosed-set lattice of a graphG. G issensitive if the following implication is always true for any graphG′: ?(G)??(G′)?(G)?GG iscritical if ?(G)??(G-e) for anye inE(G) and ?(G)??(G+e) for anye in \(\left( {\bar G} \right)\) where \(\bar G\) is the complement ofG. Every sensitive graph is, a fortiori, critical. Is every critical graph sensitive? A negative answer to this question is given in this note.  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号