A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs

We prove that, for a certain positive constant a and for an infinite set of values of n, the number of nonisomorphic triangular embeddings of the complete graph K_n is at least n^an2. A similar lower bound is also given, for an infinite set of values of n, on the number of nonisomorphic triangular embeddings of the complete regular tripartite graph K_n,n,n.     

A topological lower bound for the circular chromatic number of Schrijver graphs

In this paper, we prove that the Kneser graphs defined on a ground set of n elements, where n is even, have their circular chromatic numbers equal to their chromatic numbers. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 257–261, 2005     

一类连通无三角形图线图的共色数的下界

Erd(o)s,Gimbel and Straight (1990) conjectured that if ω(G)＜5 and z(G)＞3,then z(G)≥χ(G)-2. But by using the concept of edge cochromatic number it is proved that if G is the line graph of a connected triangle-free graph with ω(G)＜5 and G≠K4, then z(G)≥χ(G)-2.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

A lower bound on the number of removable ears of 1-extendable graphs

Let G be a 1-extendable graph distinct from K₂ and C_2n. 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.     

A lower bound for groupies in graphs

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph K_n − e contains just 2 groupie vertices for n ≥ 2. In this paper we derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. © 1996 John Wiley & Sons, Inc.     

A lower regulator bound for number fields

Lower bounds for regulators of algebraic number fields are very important for a variety of applications. Good estimates depend at least on the degree and the discriminant of the considered field. In this paper we present an improved bound which is obtained from more specific field data, e.g. the size of small T₂-values of the integers of the field. This is of considerable interest for computations in practice, for example, of fundamental units.     

A better bound for the cop number of general graphs

In this note, we prove that the cop number of any n‐vertex graph G, denoted by , is at most . Meyniel conjectured . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008     

A lower bound for the number of intermediary rings

We give a sharp lower bound for the number of intermediary rings in normal pairs. As a consequence, the exact length of maximal chains, and a sharp lower bound for the number of overrings of Prüfer domains are obtained.     

A lower estimate for the achromatic number of irreducible graphs

The achromatic number of a graph is the largest number of independent sets its vertex set can be split into in such a way that the union of any two of these sets is not independent. A graph is irreducible if no two vertices have the same neighborhood. The achromatic number of an irreducible graph with n vertices is shown to be $\text{≥(}\text{1}\text{2}\text{?0(1))log}\text{n?}\text{log log}\text{n,}$ while an example of Erdös shows that it need not be log n/log 2+2 for any n. The proof uses an indiscernibility argument.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A lower bound for the equilateral number of normed spaces

We show that if the Banach-Mazur distance between an -dimensional normed space and is at most , then there exist equidistant points in . By a well-known result of Alon and Milman, this implies that an arbitrary -dimensional normed space admits at least equidistant points, where is an absolute constant. We also show that there exist equidistant points in spaces sufficiently close to , .

     

A lower bound for the distance k-domination number of trees

A subset D of vertices of a graph G = (V, E) is a distance k-dominating set for G if the distance between every vertex of V ? D and D is at most k. The minimum size of a distance k-dominating set of G is called the distance k-domination number γ_k(G) of G. In this paper we prove that (2k + 1)γ_k(T) ≥ ¦V¦ + 2k ? kn₁ for each tree T = (V, E) with n₁ leafs, and we characterize the class of trees that satisfy the equality (2k + 1)γ_k(T) = ¦V¦ + 2k ? kn₁. Our results generalize those of Lemanska [4] for k = 1 and of Cyman, Lemanska and Raczek [1] for k = 2.     

A lower bound for the number of transitive perfect codes

We construct at least $\frac{1}{{8n^2 \sqrt 3 }}e^{\pi \sqrt {2n/3} } (1 + o(1))$ pairwise nonequivalent transitive extended perfect codes of length 4n as n → ∞.     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

A lower bound for the independence number of a planar graph

A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then $\text{α(G)/N ?}\text{2}\text{9}$.     

An upper bound for the chromatic number of line graphs

It was conjectured by Reed [B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , where Δ(G) and ω(G) are the maximum degree and clique number of G, respectively. In this paper we prove that this bound holds if G is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph G and produces a colouring that achieves our bound.