Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges.
2001 Academic Press
Let G=(V(G), E(G)) be a finite connected graph. The Cheeger number of G is
,
where X(G) is the set of all parts X/V(G) so that X{< and X =V(G)"X{<. Also, E(A, B) is the set of all A B edges in G and
Here m G (x) is the degree of the vertex x in G. For instance, the Cheeger number of the complete graph K N on N vertices is h(K N )=NΓ[2(N&1)]. Also, the Cheeger number of a claw (or star)
Given n # Z, n>0, let G(n) be the family of all finite connected graphs G admitting at least two edges e, e$ # E(G) with d G (e, e$) 2n+2. Here d G (e, e$) is the distance between the edges e and e$, i.e., the minimum number of edges in a path that connects a vertex of e and a vertex of e$. For instance, for any path P 2m+1 on 2m+1 vertices (m 3), P 2m+1 # G(n) for any 1 n m&2. Yet, K N Γ G(n) and K 1, N Γ G(n), for any n>0. Let $(G) and 2(G) be the minimum and maximum degrees of a vertex in G, respectively. We may state Theorem 1. The Cheeger number h(G) satisfies the estimate h(G) 2 2 $(G) _ 2(G)&2 -2(G)&1+ 2(G) $(G) 2 -2(G)&1&1 n+1 & (1)
for any graph G # G(n).