共查询到20条相似文献,搜索用时 250 毫秒
1.
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. 相似文献
2.
We show that a graph G with n vertices is a q-tree if and only if its chromatic polynomial is P(G, λ) = λ(λ – 1) ? (λ – q + 1) (λ – q)n-q where n ≥q. 相似文献
3.
Edward A. Bender E. Rodney Canfield Brendan D. McKay 《Random Structures and Algorithms》1990,1(2):127-169
Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions wk ? 1. a(x) and φ(x) such that c(n, q) ? wk(qN)enφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (Nq) exp(–ne?2q/n). on the other hand, if k = o(n1/2), this formula simplifies to c(n, n + k) ? 1/2 wk (3/π)1/2 (e/12k)k/2nn?(3k?1)/2. 相似文献
4.
Earl Glen Whitehead 《Journal of Graph Theory》1985,9(2):279-284
The graphs called 2-trees are defined by recursion. The smallest 2-tree is the complete graph on 2 vertices. A 2-tree on n + 1 vertices (where n ≥ 2) is obtained by adding a new vertex adjacent to each of 2 arbitrarily selected adjacent vertices in a 2-tree on n vertices. A graph G is a 2-tree on n(≥2) vertices if and only if its chromatic polynomial is equal to γ(γ - 1)(γ - 2)n—2. 相似文献
5.
We determine the maximum number of colors in a coloring of the edges of Km,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of Ka,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a2 ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004 相似文献
6.
Let G be a graph on p vertices with q edges and let r = q ? p = 1. We show that G has at most cycles. We also show that if G is planar, then G has at most 2r ? 1 = o(2r ? 1) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2r ? 1 cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255–264, 2008 相似文献
7.
Marialuisa J. de Resmini 《Journal of Geometry》1983,20(1):36-43
A k-set of type (m,n), with k=(q+√q+1)(q2?q+1), m= 1+√q, n=q+√q+1, is proved to exist in a Galois plane PG(2,q2), q a square, and its construction is given. Thus, its complement, i.e. a ((q?√q)(q+√q+1)(q2?q+1); √q(q√q?√q?1),√q(q √q?1))-set, exists too. The special case q=16 is considered and the points of a (91;3,7)-set in PG(2,16) are exhibited. A generalization is given. 相似文献
8.
Paul Vaderlind 《Journal of Graph Theory》1988,12(2):245-248
It is shown here that a connected graph G without subgraphs isomorphic to K4 is triangulated if and only if its chromatic polynomial P(G,λ) equals λ(λ ? 1)m(λ ? 2)r for some integers m ≧ 1, r ≧ 0. This result generalizes the characterization of Two-Trees given by E.G. Whitehead [“Chromaticity of Two-Trees,” Journal of Graph Theory 9 (1985) 279–284]. 相似文献
9.
Martin Erickson 《Journal of Graph Theory》1993,17(6):679-681
Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc. 相似文献
10.
For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph Gn,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions. 相似文献
11.
LetP be a finite classical polar space of rankr, r2. An ovoidO ofP is a pointset ofP, which has exactly one point in common with every totally isotropic subspace of rankr. It is proved that the polar spaceW
n
(q) arising from a symplectic polarity ofPG(n, q), n odd andn > 3, that the polar spaceQ(2n, q) arising from a non-singular quadric inPG(2n, q), n > 2 andq even, that the polar space Q–(2n + 1,q) arising from a non-singular elliptic quadric inPG(2n + 1,q), n > 1, and that the polar spaceH(n,q
2) arising from a non-singular Hermitian variety inPG(n, q
2)n even andn > 2, have no ovoids.LetS be a generalized hexagon of ordern (1). IfV is a pointset of order n3 + 1 ofS, such that every two points are at distance 6, thenV is called an ovoid ofS. IfH(q) is the classical generalized hexagon arising fromG
2
(q), then it is proved thatH(q) has an ovoid iffQ(6, q) has an ovoid. There follows thatQ(6, q), q=32h+1, has an ovoid, and thatH(q), q even, has no ovoid.A regular system of orderm onH(3,q
2) is a subsetK of the lineset ofH(3,q
2), such that through every point ofH(3,q
2) there arem (> 0) lines ofK. B. Segre shows that, ifK exists, thenm=q + 1 or (q + l)/2.If m=(q + l)/2,K is called a hemisystem. The last part of the paper gives a very short proof of Segre's result. Finally it is shown how to construct the 4-(11, 5, 1) design out of the hemisystem with 56 lines (q=3). 相似文献
12.
Olympia Talelli 《代数通讯》2013,41(3):1167-1172
Here we show that a countable group G has periodic cohomology of period q after some steps with the periodicity isomorphisms induced by cup product with an element in H q (G, ?) if and only if G has periodic homology of period q after some steps with the periodicity isomorphisms induced by cap product with an element in H q (G, ?). In [2] Asadollahi, Hajizamani, and Salarian showed that, if a group G is such that every flat ?G-module has finite projective dimension, then G has periodic cohomology of period q after some steps with the periodicity isomorphisms induced by cup product with an element in H q (G, ?) if and only if G has periodic homology of period q after some steps with the periodicity isomorphisms induced by cap product with an element in H q (G, C), where C is the cotorsion envelope of the trivial ?G-module ?. 相似文献
13.
Let G be a graph of order n ? 3. We prove that if G is k-connected (k ? 2) and the degree sum of k + 1 mutually independent vertices of G is greater than 1/3(k + 1)(n + 1), then the line graph L(G) of G is pancyclic. We also prove that if G is such that the degree sum of every 2 adjacent vertices is at least n, then L(G) is panconnected with some exceptions. 相似文献
14.
The problem of vertex labeling with a condition at distance two in a graph, is a variation of Hale’s channel assignment problem, which was first explored by Griggs and Yeh. For positive integerp ≥q, the λ p,q -number of graph G, denoted λ(G;p, q), is the smallest span among all integer labellings ofV(G) such that vertices at distance two receive labels which differ by at leastq and adjacent vertices receive labels which differ by at leastp. Van den Heuvel and McGuinness have proved that λ(G;p, q) ≤ (4q-2) Δ+10p+38q-24 for any planar graphG with maximum degree Δ. In this paper, we studied the upper bound of λ p ,q-number of some planar graphs. It is proved that λ(G;p, q) ≤ (2q?1)Δ + 2(2p?1) ifG is an outerplanar graph and λ(G;p,q) ≤ (2q?1) Δ + 6p - 4q - 1 if G is a Halin graph. 相似文献
15.
F. M. Dong K. M. Koh K. L. Teo C. H. C. Little M. D. Hendy 《Journal of Graph Theory》2001,37(1):48-77
Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ???s(p,q) (resp., ??2?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph Kp,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? 2?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ?s(p,q) (resp., G ∈ ?? 2?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ???si(p+i,q?i) where max and si = s ? i(p?q+i) (resp., a subset of ??2?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from Kp,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001 相似文献
16.
In this paper, we have defined the concept of the depth of a planar graph. We show that, if G is a simple finite planar graph with p vertices and q edges and q > 3(p ? 1) ? p/2s?1, then the depth of G is at least equal to s. 相似文献
17.
A (p, q)-graph G is said to be (k, d)-arithmetic if its vertices can be assigned distinct nonnegative integers so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices, can be arranged in the arithmetic progression k, k + d, k + 2d, …, k + (q - 1)d. In this paper we initiate a study on the structures of finite (k, d)-arithmetic graphs. 相似文献
18.
V. A. Voblyi 《Mathematical Notes》1977,21(1):36-39
Let t(r, n) be the number of trees with n vertices of which r are hanging and q are internal (r=n−9). For a fixed r or q we
prove the validity of the asymptotic formulas (r > 2)t(r, n)≈t/r|(r−2)| 22−r
n
2r−4 (n→∞)t(n−q, n)≈1/q|(q−1)|q
q−2
n
q−1 (n→∞) In the derivation of these formulas we do not use the expression for the enumerator of the trees with respect to the number
of hanging vertices.
Translated from Matematicheskie Zametki, Vol. 21, No. 1, pp. 65–70, January, 1977. 相似文献
19.
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K4, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)2. Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001 相似文献
20.
Let G be a finite group. An element g ∈ G is called a vanishing element if there exists an irreducible complex character χ of G such that χ(g)= 0. Denote by Vo(G) the set of orders of vanishing elements of G. Ghasemabadi, Iranmanesh, Mavadatpour (2015), in their paper presented the following conjecture: Let G be a finite group and M a finite nonabelian simple group such that Vo(G) = Vo(M) and |G| = |M|. Then G ≌ M. We answer in affirmative this conjecture for M = Sz(q), where q = 22n+1 and either q ? 1, \(q - \sqrt {2q} + 1\) or q + \(\sqrt {2q} + 1\) is a prime number, and M = F4(q), where q = 2 n and either q4 + 1 or q4 ? q2 + 1 is a prime number. 相似文献