首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 890 毫秒
1.
A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G)≥3κ-1/2 or δ(G)≥5κ-4.Several known results are generalized.  相似文献   

2.
A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.  相似文献   

3.
Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient cn-2 is equal to the Wiener index of G, while cn-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.  相似文献   

4.
Letk2 be an integer and let G be a graph of ordern with minimum degree at leastk, n8k -16 for evenn and n⩾6k - 13 for oddn. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycleC. G has a [k, k + 1]-factor containingC Preject supported partially by an exchange program between the Chinese Academy of Sciences and the Japan Society for Promotion of Sciences and by the National Natural Science Foundation of China (Grant No. 19136012)  相似文献   

5.
Let G be a connected claw-free graph on n vertices. Let ς3(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς3(G) ≥ n − 3 then G is traceable or else G is one of graphs Gn each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K3. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς3(G) ≥ nk, n > ν(k) and G is non-traceable, then G is a factor of a graph Gn. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς3(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998  相似文献   

6.
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.  相似文献   

7.
8.
Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.  相似文献   

9.
An edge e of a k-connected graph G is said to be a removable edge if Ge is still k-connected, where Ge denotes the graph obtained from G by deleting e to get Ge, and for any end vertex of e with degree k − 1 in Ge, say x, delete x, and then add edges between any pair of non-adjacent vertices in N Ge (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).  相似文献   

10.
The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k) the set of connected graphs with n vertices and k cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield-Simmons index, respectively, among all graphs in G(n,k) for all possible k values.  相似文献   

11.
A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay(K, S) for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as (N, R), is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π(N) of a network (N, R), defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank(G) ≤ 50.  相似文献   

12.
The Wiener index of a graph G is defined as W(G)=∑ u,v d G (u,v), where d G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order nk; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.  相似文献   

13.
A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices.  相似文献   

14.
15.
It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.  相似文献   

16.
Let G be a finite simple graph with adjacency matrix A, and let P(A) be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P(A). In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.  相似文献   

17.
A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v 1, v 2, ..., v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v 1, v 2, ..., v i }] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.  相似文献   

18.
In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph Gn,k, where Gn,k is obtained from the complete graph Kn-k by attaching paths of almost equal lengths to all vertices of Kn-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.  相似文献   

19.
For a fixed (multi)graph H, a graph G is H‐linked if any injection f: V(H)→V(G) can be extended to an H‐subdivision in G. The notion of an H ‐linked graph encompasses several familiar graph classes, including k‐linked, k‐ordered and k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012  相似文献   

20.
In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤pk, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph Knk-list critical. While this is the case for all 5≤kn, Kn is not 4-list critical if n is large.  相似文献   

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

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