Odd Components of Co-Trees and Graph Embeddings ^{1}

Han Ren, Dengju Ma and Junjie Lu

Department of Mathematics, East China Normal University, Shanghai 200062, P.C.China

Abstract: In this paper we investigate the relation between odd components of co-trees and graph embeddings. We show that any graph G must share one of the following two conditions: (a) for each integer h such that G may be embedded on S_{h}, the sphere with h handles, there is a spanning tree T in G such that h = \frac{1}{2}(β(G)−ω(T)), where β(G) and ω(T) are, respectively, the Betti number of G and the number of components of G − E(T) having odd number of edges; (b) for every spanning tree T of G, there is an orientable embedding of G with exact ω(T) + 1 faces. This extends Xuong and Liu’s theorem[5,6] to some other ( possible ) genera. Infinitely many examples show that there are graphs which satisfy (a) but (b). Those make a correction of a rseult of D.Archdeacon[2, theorem 1].

Key Words Odd component of co-trees, graph embeddings.

AMS Subject Classification (2000) 05C10, 05C30

I. Introduction

Graphs here are simple connected. All the terms and notations are standard and may be found in [3].

A surface is a compact 2-manifold. An orientable surface, denoted by S_{g}, is the sphere with g handles. An embedding of a graph G is a drawing of G in a surface Σ such that no edge-crossing is permitted and each component of Σ − G is an open disc. Let T be a spanning tree of G. By ω(T) we mean the number of the components of the co-tree G − E(T) having odd number of edges. It is well known that odd components of co-trees play a key role in graph embeddings and there have been many literatures for it. The following result is due to Xuong and Liu[5,6].

Theorem A Let G be a graph. Then the maximum genus of G is

γ_{M}(G) = \frac{1}{2}(β(G) − min\{ω(T)\}),

where β(G) is the Betti number of G and the min is taken over all the spanning trees in G.

Another well known result is the following Duke’s interpolation theorem[4] for genera of orientable surfaces on which a graph may be embedded.

Theorem B If a graph G may be embedded in S_{h} and S_{k}(h ≤ k), then it also may be embedded in S_{g} for g = h, h + 1, ..., k.

1Supported by NNSF of China under granted number 10271048

Theorem B says that the genera of orientable surfaces on which a graph may be embedded form a series of consecutive integer numbers. We write [γ(G), γ_{M}(G)] as the genera interval of a graph G, where γ(G) and γ_{M}(G) are, respectively, the minimum genus ( or genus in short ) and the maximum genus of G.

One of the main result of this paper is to establish an interpolation theorem for odd components of co-trees in a graph, i.e., the following

Theorem 1. Let G be a graph with two spanning trees T_{1} and T_{2}. Then we have that

(a) ω(T_{1}) ≡ ω(T_{2})(mod 2) and

(b) for each integer m with ω(T_{1}) ≤ m ≤ ω(T_{2}) and m ≡ ω(T_{1}), there is a spanning tree T in G such that ω(T) = m.

If we denote g = \frac{1}{2}(β(G)−ω(T)) for each spanning tree T in G, then Theorem 1 shows that all the integers defined this way form a collection of consecutive integers. Define [g_{m}(G), g_{M}(G)] as the odd components interval of G, where

g_{m}(G) =\frac{1}{2}(β(G) − max\{ω(T)\}),
g_{M}(G) =\frac{1}{2}(β(G) − min\{ω(T)\}).

It follows from Theorem A that g_{M} = γ_{M}(G). Thus, we have that for each graph G, either [γ(G), γ_{M}(G)] ⊆ [g_{m}(G), g_{M}(G)] or [g_{m}(G), g_{M}(G)] ⊆ [γ(G), γ_{M}(G)]. If [γ(G), γ_{M}(G)] ⊆ [g_{m}(G), g_{M}(G)], then for every surface S_{h} with γ(G) ≤ h ≤ γ_{M}(G), there is a spanning tree T such that

h = \frac{1}{2}(β(G) − w(T)).

Otherwise, for each spanning tree T in G, there is an orientable surface S_{h} on which G may be embedded and have exact ω(T) + 1 faces,i.e., the following

Theorem 2. Let G be a connected graph with the parameters γ(G), γ_{M}(G), g_{m} and g_{M} defined as above. Then G must satisfy one of the following conditions:

(a) for every surface S_{h} on which G may be embedded, there is a spanning tree T in G such that h = \frac{1}{2}(β(G) − ω(T));

(b) for every spanning tree T of G, G may be embedded in some orientable surface which has exact ω(T) + 1 faces.

Remark: (1). Theorem 2 does extend Xuong and Liu’s result (i.e., Theorem A) to some other ( possible ) surfaces since for each integer h ∈ [γ(G), γ_{M}(G)] ⋂ [g_{m}(G), g_{M}(G)], there is a spanning tree T such that h = \frac{1}{2}(β(G) − ω(T)); (2) the readers with care may notice that the partial result of Theorem 2 (i.e., (b) of Theorem 2) was stated in Archdeacon’s paper[2]. Here, what we will see is that there are infinitely many graphs which do not satisfy the condition (b) of Theorem 2. Hence, Theorem 2 also makes a correction of a result in [2, theorem 1].(3) Theorem 2 may find its uses in graphs with a spanning tree whose co-tree has large number of odd components. In particular, we have the following result:

Corollary. Let G be a cubic hamiltonian graph. If G is nonplanar, then for every orientabl surface S_{g} on which G may be embedded, there is a spanning tree T in G such that g = \frac{1}{2}(β(G) − ω(T)).

II. Proof of Main Results

In this section we shall prove Theorems 1 and 2. We first present the following result for tree-transformation and their odd component numbers of co-trees.

Lemma 1. Let G be a connected graph with a spanning tree T. Let e be an edge in G − E(T) and f is another edge in C_{e} − e, where C_{e} is the unique cycle in T + e. Then T′ = T + e − f is another spanning tree in G such that ω(T′) ≡ ω(T)(mod 2) and | ω(T′) − ω(T) |≤ 2.

Proof. Let σ_{e} be the component of G − E(T) containing e. Let σ_{x} and σ_{y} be, respectively, the ( possible) two components of G − E(T) containing x and y, where f = (x, y). Then there are several more cases should be handled as listed below.

(1). σ_{e}, σ_{x} and σ_{y} are pairewise distinct components; (2) σ_{x} = σ_{y} ≠ σ_{e}; (3) σ_{x} = σ_{e} ≠ σ_{y}; (4) σ_{y} = σ_{e} ≠ σ_{x}; (5) σ_{y} = σ_{x} = σ_{e}.

Now we consider the case that σ_{e}, σ_{x} and σ_{y} are pairewise distinct components. We concentrate on the case (1).

There are two subcases to be handled.

Subcase 1.1. σ_{e} − e is disconnected.

Let σ_{e} − e = σ′_{e} − σe^{′′}.

(a).If |σe^{′′}| = |σ′_{e}| ≡ 1(mod 2), then after simple countings we see that

ω(T′) = \{ \begin{matrix}ω(T), & |σ_{x}| − |σ_{y}| ≡ 0(mod 2); \\ ω(T) − 2, & |σ_{x}| − |σ_{y}| ≡ 1(mod 2). \end{matrix}

(b). If |σe^{′′}| = |σ′_{e}| ≡ 0(mod 2), then as we did in (a) one may see that ω(T′) = ω(T) or ω(T) − 2.

If |σ_{e}| ≡ 0(mod 2), then |σ′_{e}|−|σe^{′′}| ≡ 1(mod 2). By repeating a similar procedure as we used we have that ω(T′) = ω(T) or ω(T) + 2.

Subcase 1.2 σ_{e}−e is connected. This time we may find that ω(T′) ≡ ω(T)(mod 2) if we follow the same trace of proving procedure in Subcase 1.1. This completes the proof in the case that σ_{e}, σ_{x} and σ_{y} are pairewise distinct. Other situations may be handled in the same way. This finishes the proof of Lemma 1. □

The following result says that the tree graph of a connected graph is connected.

Lemma 2 ([3,pp41]). Let G be a connected graph. Then any two spanning trees in G may be transformed through finite number of the tree transformation as stated in Lemma 1.

Based on the results in Lemmas 1 and 2, Theorem 1 follows. □

As for proof of Theorem 2, one may see that it follows from Theorem A, Theorem 1 and Euler Equation for graphs on surfaces. This finishes the proof of Theorem 2.□

III. Counter-examples

In this section we shall present infinitely many cubic hamiltonian graphs which may not embedded in S_{1}, the torus. That is, each of those graphs has a hamiltonian path ( i.e., a spanning tree ) P such that the present graph can not be embedded into an orientable surface with exact ω(P) + 1 faces. Those are counter-examples for a result in [2,Theorem 1].

We start from a class of 4-regular graphs called circular graphs. They are defined as follows. Let n and k be a pair of natural numbers with 0 < k < ⌊\frac{n}{2}⌋. Then we may define the 4-regular graph C(n, k) as a n-cycle C_{n} = (1, 2, 3, ..., n) together with the chords (i, i + k) for 1 ≤ i ≤ n. It is clear that the circular graph with the form C(n, k) are all non-planar as n is large enough and k(≥ 3) remains fixed. Now we draw the n-cycle C_{n} into the plane and all the chords of the form (i, i + k) in straight segment such that they all are contained in the same component of S_{0} −C_{n}. Edges on C_{n} are called r-edges while others are b-edges. Under the local semi-edge permutation of the four edges around each vertex, the order is r, r, b, b. Now we splitting each vertex such that every pair of b, b edges remain incident while the corresponding two r, r edges are also incident. Then the resulting graph is in fact the well-known cubic graph called generalized petersen graph ( or petersen graph in short). It is clear that every petersen graph may be obtained this way. The following result is easy to be verified.

Lemma 3. Every circular graph C(n, k) may be embedded in the torus such that each face is bounded by a 4-cycle (i, i + 1, i + k + 1, i + k)(1 ≤ i ≤ n).

The next result shows that an embedding of a petersen graph G(n, k) in an orientable surface may induce an embedding of C(n, k) in the same surface.

Lemma 4. Let G(n, k) be a petersen graph embedded in S_{g}. Then C(n, k) may also be embedded on S_{g} such that for each vertex x of C(n, k), the local permutation of 4 edges incident to x are of type r, r, b, b edges as defined before.

Proof. This follows from the fact that C(n, k) is a minor of G(n, k) by definition and shrinking some ( possible ) edges ( in a 1-factor) will determine a new embedding for the resulting graph C(n, k). □.

Now we consider the situation that k = 4 and n is large enough. Then it is clear that C(n, 4) may be uniquely embedded on S_{1} since the 4-cycle contained in C(n, 4) are of the form (i, i + 1, i + 5, i + 4). If a petersen graph G(n, 4) may be embedded in S_{1}, then C(n, 4) will have at least two distinct embeddings on S_{1}, a contradiction as desired. So, we have

Lemma 5. If n is a natural number large enough, then the petersen graph G(n, 4) may not embedded in S_{1}.

The following result says that almost all the types of petersen graphs are hamiltonian. In particular, G(n, 4) is hamiltonian as n is large enough.

Lemma 6.[1] A petersen graph G(n, k) is not hamiltonian if and only k = 2 and n ≡ 5(mod 6).

Lemmas 5 and 6 show that there are infinitely many cubic hamiltonian graph G which is non-planar and contains a hamiltonian path ( hence a spanning tree) P such that G can not be embedded in S_{1}, i.e., G can not be embedded in any orientable surface which has exact ω(P) + 1 faces!

References

[1] B.R.Alspach, The Classification of Hamiltonian Generalized Petersen Graphs, J. Combin. Theory Ser. B. 34 (1983), 293-312.

[2] D. Archdeacon, C.Paul Bonningtong and J. Siran A Nebeský-Type Characterization for Relative Maximum Genus, J. Combin. Theory Ser. B 73 (1998) 77-98.

[3] J.A.Bondy and U.S.R.Murty, Graphs Theory with Applications, Macmilan Press Ltd., (1976)

[4] R.A.Duke, The genus, regional Number, and Betti Number of a graph, Canad.J. Math., 26, (1966), 817-822.

[5] Yanpei Liu, The maximum orientable genus of a graph, Scientia Sinica Special Issue on Math.,II (1979),41-55.

[6] N.H.Xuong, How to Determine the Maximum Genus of a Graph, J. Combin. Theory Ser. B., (1979),217-225.