共查询到10条相似文献,搜索用时 92 毫秒
1.
A bicyclic graph is a connected graph in which the number of edges equals the number of vertices plus one. Let Δ(G) and ρ(G) denote the maximum degree and the spectral radius of a graph G, respectively. Let B(n) be the set of bicyclic graphs on n vertices, and B(n,Δ)={G∈B(n)∣Δ(G)=Δ}. When Δ≥(n+3)/2 we characterize the graph which alone maximizes the spectral radius among all the graphs in B(n,Δ). It is also proved that for two graphs G1 and G2 in B(n), if Δ(G1)>Δ(G2) and Δ(G1)≥⌈7n/9⌉+9, then ρ(G1)>ρ(G2). 相似文献
2.
Medha Dhurandhar 《Discrete Mathematics》1982,42(1):51-56
Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K5?e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G). 相似文献
3.
《Discrete Mathematics》2002,231(1-3):257-262
Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2. 相似文献
4.
In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then , where α(G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ∈{7,…,19}. 相似文献
5.
Let G be a finite group. The prime graph of G is denoted by Γ(G). In this paper, as the main result, we show that if G is a finite group such that Γ(G) = Γ(2 D n (3α)), where n = 4m+ 1 and α is odd, then G has a unique non-Abelian composition factor isomorphic to 2 D n (3α). We also show that if G is a finite group satisfying |G| = |2 D n (3α)|, and Γ(G) = Γ(2 D n (3α)), then G ? 2 D n (3α). As a consequence of our result, we give a new proof for a conjecture of Shi and Bi for 2 D n (3α). Application of this result to the problem of recognition of finite simple groups by the set of element orders are also considered. Specifically, it is proved that 2 D n (3α) is quasirecognizable by the spectrum. 相似文献
6.
Let G be any graph, and also let Δ(G), χ(G) and α(G) denote the maximum degree, the chromatic number and the independence number of G, respectively. A chromatic coloring of G is a proper coloring of G using χ(G) colors. A color class in a proper coloring of G is maximum if it has size α(G). In this paper, we prove that if a graph G (not necessarily connected) satisfies χ(G)≥Δ(G), then there exists a chromatic coloring of G in which some color class is maximum. This cannot be guaranteed if χ(G)<Δ(G). We shall also give some other extensions. 相似文献
7.
A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r Δ > 2 cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P n k , the kth power of a path P n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K 3) > cn. We show that, given Δ and H, there are β>0 and n 0 such that, if G is a connected graph on n≥n 0 vertices with maximum degree at most Δ and bandwidth at most β n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn. 相似文献
8.
This paper solves for torsion free and torsion abelian groups G the problem of presenting nth powers Δn(G) of the augmentation ideal Δ(G) of an integral group ring , in terms of the standard additive generators of Δn(G). A concrete basis for Δn(G) is obtained when G itself has a basis and is torsion. The results are applied to describe the homology of the sequence Δn(N)G?Δn(G)?Δn(G/N). 相似文献
9.
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γr(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γt(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γr(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γt(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γt(G)=n-Δ. 相似文献
10.
Let G be a 1-extendable graph distinct from K2 and C2n. A classical result of Lovász and Plummer (1986) [5, Theorem 5.4.6] states that G has a removable ear. Carvalho et al. (1999) [3] proved that G has at least Δ(G) edge-disjoint removable ears, where Δ(G) denotes the maximum degree of G. In this paper, the authors improve the lower bound and prove that G has at least m(G) edge-disjoint removable ears, where m(G) denotes the minimum number of perfect matchings needed to cover all edges of G. 相似文献