首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 537 毫秒
1.
The nth crossing number of a graph G, denoted ncr(G), is the minimum number of crossings in a drawing of G on an orientable surface of genus n. We prove that for every a>b>0, there exists a graph G for which 0cr(G)=a, 1cr(G)=b, and 2cr(G)=0. This provides support for a conjecture of Archdeacon et al. and resolves a problem of Salazar.  相似文献   

2.
LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′c(G) ≤δ. If χ′c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.  相似文献   

3.
The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized.  相似文献   

4.
Let G be a connected graph. The subdivision graph of G, denoted by S(G), is the graph obtained from G by inserting a new vertex into every edge of G. The triangulation graph of G, denoted by R(G), is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. In this paper, we first provide complete information for the eigenvalues and eigenvectors of the probability transition matrix of a random walk on S(G) (res. R(G)) in terms of those of G. Then we give an explicit formula for the expected hitting time between any two vertices of S(G) (res. R(G)) in terms of those of G. Finally, as applications, we show that, the relations between the resistance distances, the number of spanning trees and the multiplicative degree-Kirchhoff index of S(G) (res. R(G)) and G can all be deduced from our results directly.  相似文献   

5.
The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.  相似文献   

6.
Suppose G is a simple connected n‐vertex graph. Let σ3(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ3G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K1,3. Second, if σ3(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ3(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K2,3 or K (the 6‐vertex graph obtained from K2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004  相似文献   

7.
A square matrix over the complex field with non-negative integral trace is called a quasi-permutation matrix. For a finite group G the minimal degree of a faithful permutation representation of G is denoted by p(G). The minimal degree of a faithful representation of G by quasi-permutation matrices over the rational and the complex numbers are denoted by q(G) and c(G) respectively. Finally r(G) denotes the minimal degree of a faithful rational valued complex character of G. In this paper p(G), q(G), c(G) and r(G) are calculated for the groups PSU (3, q2) and SU (3, q2).AMS Subject Classification (2000): 20C15  相似文献   

8.
A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χp(G).In this paper, we prove that χp(G)≤118 for every 2-connected plane graph G.  相似文献   

9.
Some results on spanning trees   总被引:2,自引:0,他引:2  
Some structures of spanning trees with many or less leaves in a connected graph are determined.We show(1) a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and(2) a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ(G) =Δ(T) and the number of leaves of T is not greater than n D(G)+1,where D(G) is the diameter of G.  相似文献   

10.
Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.  相似文献   

11.
An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.  相似文献   

12.
Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.  相似文献   

13.
A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χp(G).In this paper we prove that χp(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χp(G)=10. If a 2-connected outerplane graph G is bipartite, then χp(G)≤8, moreover, this bound is best possible.  相似文献   

14.
Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions   总被引:1,自引:0,他引:1  
An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c¢vd(G){\chi'_{vd}(G)}. It is proved that c¢vd(G) £ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s2(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ 2(G) denotes the minimum degree sum of two nonadjacent vertices in G.  相似文献   

15.
A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number rc(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that rc(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper rc(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, rc(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.  相似文献   

16.
Dongseok Kim  Jaeun Lee   《Discrete Mathematics》2008,308(22):5078-5086
If we fix a spanning subgraph H of a graph G, we can define a chromatic number of H with respect to G and we show that it coincides with the chromatic number of a double covering of G with co-support H. We also find a few estimations for the chromatic numbers of H with respect to G.  相似文献   

17.
Given a graph G with n vertices, we call ck(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound ck(G) from the minimum degree and the order of the graph.  相似文献   

18.
Let H be a cubic graph admitting a 3-edge-coloring c:E(H)→Z3 such that the edges colored with 0 and μ∈{1,2} induce a Hamilton circuit of H and the edges colored with 1 and 2 induce a 2-factor F. The graph H is semi-Kotzig if switching colors of edges in any even subgraph of F yields a new 3-edge-coloring of H having the same property as c. A spanning subgraph H of a cubic graph G is called a semi-Kotzig frame if the contracted graph G/H is even and every non-circuit component of H is a subdivision of a semi-Kotzig graph.In this paper, we show that a cubic graph G has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn [L.A. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988], and Häggkvist and Markström [R. Häggkvist, K. Markström, Cycle double covers and spanning minors I, J. Combin. Theory Ser. B 96 (2006) 183-206].  相似文献   

19.
(3,k)-Factor-Critical Graphs and Toughness   总被引:1,自引:0,他引:1  
 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and kn−7. Revised: September 21, 1998  相似文献   

20.
The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D2(G),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D2(G) = D(G). © 1997 John Wiley & Sons, Inc.  相似文献   

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

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