共查询到20条相似文献,搜索用时 31 毫秒
1.
G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c2v)], where cv is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+>n?(n?L(G))≥n?(n?λ1) and that χ(G)≥ n?(n?λ1); λ1 is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds. 相似文献
2.
Simonovits Miklós 《Journal of Combinatorial Theory, Series B》1974,17(1):69-79
P. Turán has asked the following question:Let I12 be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gn of n vertices if Gn does not contain I12 as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I12. This graph Hn can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [] or vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes. 相似文献
3.
Let denote the complement of a graph G, and x(G), β1(G), β4(G), α0(G), α1(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order . Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β1(G) + α1(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of , since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G. 相似文献
4.
M.K Grammatikopoulos Y.G Sficas V.A Staikos 《Journal of Mathematical Analysis and Applications》1979,67(1):171-187
We regard a graph G as a set {1,…, v} together with a nonempty set E of two-element subsets of {1,…, v}. Let p = (p1,…, pv) be an element of nv representing v points in n and consider the realization G(p) of G in n consisting of the line segments [pi, pj] in n for {i, j} ?E. The figure G(p) is said to be rigid in n if every continuous path in nv, beginning at p and preserving the edge lengths of G(p), terminates at a point q ? nv which is the image (Tp1,…, Tpv) of p under an isometry T of n. We here study the rigidity and infinitesimal rigidity of graphs, surfaces, and more general structures. A graph theoretic method for determining the rigidity of graphs in 2 is discussed, followed by an examination of the rigidity of convex polyhedral surfaces in 3. 相似文献
5.
David M. Mason 《Stochastic Processes and their Applications》1983,15(1):99-109
Let Gn denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between Gn(u) and u of the forms 6wv(u)Dn(u)6 and 6wv(Gn(u))Dn(u)6, where Dn(u) = Gn(u)?u, wv(u) = (u(1?u))?1+v and 0 ? v < is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function wv with ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function wv with 0 ? v < are potentially applicable in the construction of confidence contours for the extreme tails of a distribution. 相似文献
6.
Yoko Usami 《Discrete Mathematics》1983,44(2):195-199
A simple graph with n vertices is called Pi-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P2- and Pi-connected are obtained. Namely if , then |E(G)|?((4i?5)/(2i?2))(n?1), and if , then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former. 相似文献
7.
Jerrold R. Griggs 《Discrete Mathematics》1979,28(1):37-47
It is shown that the interval number of a graph on n vertices is at most , and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K[n/2],[n/2]. 相似文献
8.
George B Purdy 《Journal of Combinatorial Theory, Series A》1974,17(1):131-133
There are at most 2n spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is if n is odd and if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory. 相似文献
9.
For finite graphs F and G, let NF(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If and are families of graphs, it is natural to ask then whether or not the quantities NF(G), F∈, are linearly independent when G is restricted to . For example, if = {K1, K2} (where Kn denotes the complete graph on n vertices) and is the family of all (finite) trees, then of course NK1(T) ? NK2(T) = 1 for all T∈. Slightly less trivially, if = {Sn: n = 1, 2, 3,…} (where Sn denotes the star on n edges) and again is the family of all trees, then Σn=1∞(?1)n+1NSn(T)=1 for all T∈. It is proved that such a linear dependence can never occur if is finite, no F∈ has an isolated point, and contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear). 相似文献
10.
Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v0, v1,…, vn?1} and edge set E satisfies vivj?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p2, and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p2 where p is an odd prime, or n is divisible by 24. 相似文献
11.
Siddani Bhaskara Rao 《Journal of Combinatorial Theory, Series B》1979,27(1):13-41
A graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G ? S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ? S, we have dG(u) > dG(v), where dG(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph . It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and . 相似文献
12.
A function diagram (f-diagram) D consists of the family of curves {ñ} obtained from n continuous functions . We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the fi are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of . Computational complexity results are obtained for recognizing such graphs. 相似文献
13.
Best upper and lower bounds, as functions of n, are obtained for the quantities and , where β2(G) denotes the total matching number and α2(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α2(G)+β2(G), when G is a connected graph. 相似文献
14.
An ordered colouring of a graph with k colours is a vertex colouring with colours {1, 2,…,k} such that each vertex coloured j is joined to at least one vertex-of colour i for each i less than j. Examples of ordered colourings are those produced by the greedy colouring algorithm. Some properties are investigated of τ(G), the maximum k for which the graph G has an ordered k-colouring (in fact τ(G) is an upper bound for the number of colours used by the greedy algorithm). It is shown that if G has order n, then . 相似文献
15.
16.
Tom Brylawski 《Discrete Mathematics》1977,18(3):243-252
In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if X(G) = Σμ(0, x)λr ? r(x) = Σ (?1)r ? kWkλk is the characteristic polynomial of G, then Thus γ(G) ? 2r ? 1 (n+2), where γ(G) = Σwk. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then |μ| ? (r? 1)n; and γ ? (2r ? 1 ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, , and then . Further, if β is the Crapo invariant, then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network. 相似文献
17.
William T. Trotter 《Discrete Mathematics》1979,28(3):303-313
F.S. Roberts defined the boxicity of a graph G as the smallest positive integer n for which there exists a function F assigning to each vertex x?G a sequence F(x)(1),F(x)(2),…, F(x)(n) of closed intervals of R so that distinct vertices x and y are adjacent in G if and only if F(x)(i)∩F(y)(i)≠? fori = 1, 2, 3, …, n. Roberts then proved that if G is a graph having 2n + 1 vertices, thentheboxicityofGisatmostn. In this paper, we provide an explicit characterization of this inequality by determining for each n ? 1 the minimum collection n of graphs so that a graph G having 2n + 1 vertices has boxicity n if and only if it contains a graph from n as an induced subgraph. We also discuss combinatorial connections with analogous characterization problems for rectangle graphs, circular arc graphs, and partially ordered sets. 相似文献
18.
Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that . Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log2n + n vertices such that End(G) is isomorphic to M. 相似文献
19.
Elmer K Hayashi 《Journal of Number Theory》1981,13(2):176-191
Let Rk(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that , and R. C. Vaughan has shown that the relation Rk(n) = G(n) + o(nδ log?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cnβ, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term. 相似文献
20.
Medha Dhurandhar 《Journal of Combinatorial Theory, Series B》1984,37(3):210-220
Here quadratic and cubic σ-polynomials are characterized, or, equivalently, chromatic polynomials of the graphs of order p, whose chromatic number is p ? 2 or p ? 3, are characterized. Also Robert Korfhage's conjecture that if σ2 + bσ + a is a σ-polynomial then is verified. In general, if σ(G) = Σ0naiσi is a σ-polynomial of a graph G, then an?2 is determined. 相似文献