검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

KYUNGPOOK Math. J. 2019; 59(4): 797-820

Published online December 23, 2019

Copyright © Kyungpook Mathematical Journal.

Cross-index of a Graph

Akio Kawauchi∗, Ayaka Shimizu and Yoshiro Yaguchi

Osaka City University Advanced Mathematical Institute, Sugimoto, Sumiyoshi-ku, Osaka 558-8585, Japan
e-mail : kawauchi@sci.osaka-cu.ac.jp
Department of Mathematics, National Institute of Technology, Gunma College, 580 Toriba-cho, Maebashi-shi, Gunma 371-8530, Japan
e-mail : shimizu@nat.gunma-ct.ac.jp and yaguchi-y@nat.gunma-ct.ac.jp

Received: January 14, 2018; Revised: February 11, 2019; Accepted: February 13, 2019

For every tree T, we introduce a topological invariant, called the T-cross-index, for connected graphs. The T-cross-index of a graph is a non-negative integer or infinity according to whether T is a tree basis of the graph or not. It is shown how this cross-index is independent of the other topological invariants of connected graphs, such as the Euler characteristic, the crossing number and the genus.

Keywords: based graph, crossing number, genus, nullity, cross-index. The fi,rst author was supported by JSPS KAKENHI Grant Number 24244005.

A based graph is a pair (G; T) such that G is a connected graph and T is a maximal tree of G, called a tree basis of G. A based diagram (D;X) of the based graph (G; T) is defined in § 2. Then the crossing number c(G; T) of the based graph (G, T) is defined to be the minimum of the crossing numbers c(D;X) for all based diagrams (D;X) of (G; T). The genus g(D;X), the nullity ν(D;X) and the cross-index ɛ(D;X) are defined by using the ℤ2-form

ɛ:2[D;X]×2[D;X]2

on (D;X), which are invariants of non-negative integer values of the based diagram (D;X). The genus g(G; T) and the cross-index ɛ(G; T) are defined to be the minimums of the genera g(D;X) and the cross-indexes ɛ(D;X) for all based diagrams (D;X) of (G; T), respectively, whereas the nullity ν(G; T) is defined to be the maximum of the nullities ν(D;X) for all based diagrams (D;X) of (G; T). Thus, c(G; T), g(G; T), ν(G; T), ɛ(G; T) are topological invariants of the based graph (G; T). The relationships between the topological invariants c(G; T), g(G; T), ν(G; T), ɛ(G; T) of (G; T), the genus g(G) and the Euler characteristic χ(G) of the graph G are explained in § 2. In particular, the identities

c(G;T)=ɛ(G;T),         g(G;T)=g(G),         ν(G;T)=1-χ(G)-2g(G)

are established. In particular, it turns out that the crossing number c(G; T) of (G; T) is a calculable invariant in principle. The idea of a cross-index is also applied to study complexities of a knitting pattern in [5].

For a tree T, this invariant c(G; T) is modified as follows into a topological invariant cT (G), called the T-cross-index, of a graph G.

Define cT (G) to be the minimum of the invariants c(G; T′) for all tree bases T′ of G homeomorphic to T. If there is no tree basis of G homeomorphic to T, then define cT (G) = ∞.

Let c*(G) be the family of the invariants cT (G) for all trees T. The minimal value cmin(G) in the family c*(G) has appeared as the crossing number of a Γ-unknotted graph in the paper [3] on spatial graphs. The crossing number c(G) of a graph G is defined to be the minimum of the crossing numbers c(D) of all diagrams D of G (in the plane). It is an open question whether cmin(G) is equal to the crossing number c(G) of any connected graph G.

The finite maximal value cmax(G) in the family c*(G) is a well-defined invariant, because there are only finitely many tree bases of G. In the inequalities

cmax(G)cmin(G)c(G)g(G)

for every connected graph G which we establish, the following properties are mutually equivalent:

(i) G is a planar graph.

(ii) cmax(G) = 0.

(iii) cmin(G) = 0.

(iv) c(G) = 0.

(v) g(G) = 0.

In § 3, the case of the n-complete graph Kn (n ≥ 5) is discussed in a connection to Guy’s conjecture on the crossing number c(Kn). It is shown that cmin(K5) = cmax(K5) and cmin(Kn) < cmax(Kn) for every n ≥ 6. Thus, the invariants cmin(G) and cmax(G) are different invariants for a general connected graph G.

The main purpose of this paper is to show that the family c*(G) is more or less a new invariant. For this purpose, for a real-valued invariant I(G) of a connected graph G which is not bounded when G goes over the range of all connected graphs, we introduce a virtualized invariant Ĩ(G) of G which is defined to be Ĩ(G) = f(I(G)) for a fixed non-constant real polynomial f(x) in x. Every time a different non-constant polynomial f(t) is given, a different virtualized invariant Ĩ(G) is obtained from the invariant I(G). Then the main result is stated as follows, showing a certain independence between the cross-index c*(G) and the other invariants c(G), g(G), χ(G).

Theorem 4.1

Let c̃max(G), (G), (G), χ̃(G) be any virtualized invariants of the invariants cmax(G), c(G), g(G), χ(G), respectively. Every linear combination of the invariants c̃max(G), (G), (G), χ̃(G) in real coefficients including a non-zero number is not bounded when G goes over the range of all connected graphs.

The proof of this theorem is given in § 4.

As an appendix, it is shown how the non-isomorphic tree bases are tabulated in case of the complete graph K11. This tabulation method is important to compute the T-cross index cT (Kn) for a tree basis T of Kn, because we have cT (Kn) = c(Kn; T) for every tree basis T (see Lemma 3.1).

By a graph, a connected graph G with only topological edges and without vertexes of degrees 0, 1 and 2 is meant. Let G have n(≥ 1) vertexes and s(≥ 1) edges. By definition, if n = 1 (that is, G is a bouquet of loops), then every tree basis T of G has one vertex. A diagram of a graph G is a representation D of G in the plane so that the vertexes of G are represented by distinct points and the edges of G are represented by arcs joining the vertexes which may have transversely meeting double points avoiding the vertexes. A double point on the edges of a diagram D is called a crossing of D. In this paper, to distinguish between a degree 4 vertex and a crossing, a crossing is denoted by a crossing with over-under information except in Figs. 7, 8 representing diagrams of the graphs K11 and K12 without degree 4 vertexes. A tree diagram of a tree T is a diagram X of T without crossings. A based diagram of a based graph (G; T) is a pair (D;X) where D is a diagram of G and X is a sub-diagram of D such that X is a tree diagram of the tree basis T without crossings in D. In this case, the diagram X is called a tree basis diagram. The following lemma is used without proof in the author’s earlier papers [3, 4].

Lemma 2.1

Given any based graph (G; T) in3, then every spatial graph diagram of G is transformed into a based diagram (D;X) of (G; T) only with crossings with over-under information by the Reidemeister moves I–V (see Fig. 1).

Proof

In any spatial graph diagram D′ of G, first transform the sub-diagram D(T) of the tree basis T in D′ into a tree diagram X by the Reidemeister moves I–V. Since a regular neighborhood N(X;ℝ2) of X in the plane ℝ2 is a disk, a based diagram is obtained by shrinking this tree diagram into a very small tree diagram within the disk by the Reidemeister moves I–V. See Fig. 2 for this transformation. Thus, we have a based diagram (D;X) of (G; T) only with crossings with over-under information.

The crossing number c(D) of a based diagram (D;X) is denoted by c(D;X). The crossing number c(G; T) of a based graph (G; T) is the minimal number of the crossing numbers c(D;X) of all based diagrams (D;X) of (G; T). For a based diagram (D;X) of (G; T), let N(X;D) = DN(X;ℝ2) be a regular neighborhood of X in the diagram D. Then the complement cl(DN(X;D)) is a tangle diagram of m-strings ai (i = 1, 2, . . . , m) in the disk Δ = S2N(X;ℝ2) where S2 = ℝ2∪{∞} denotes the 2-sphere which is the one-point compactification of the plane ℝ2.

Let ℤ2[D;X] be the ℤ2 vector space with the arcs ai (i = 1, 2, . . . , m) as a ℤ2-basis. For any two arcs ai and aj with ij, the cross-index ɛ(ai, aj) is defined to be 0 or 1 according to whether the two boundary points ∂aj of the arc aj are in one component of the two open arcs Δ∂ai or not, respectively. For i = j, the identity ɛ(ai, aj) = 0 is taken. Then the cross-index ɛ(ai, aj) (mod 2) defines the symmetric bilinear ℤ2-form

ɛ:2[D;X]×2[D;X]2,

called the ℤ2-form on (D;X). The genus g(D;X) of the based diagram (D;X) is defined to be half of the ℤ2-rank of the ℤ2-form ɛ : ℤ2[D;X] × ℤ2[D;X] → ℤ2, which is seen to be even since the ℤ2-form ɛ is a ℤ2-symplectic form.

The genus g(G; T) of a based graph (G; T) is the minimum of the genus g(D;X) for all based diagrams (D;X) of (G; T). The following lemma shows that the genus g(G) of a graph G is calculable from based diagrams (D;X) of any based graph (G; T) of G.

Lemma 2.2

(Genus Lemma) g(G) = g(D;X) = g(G; T) for any based diagram (D;X) of any based graph (G, T).

Proof

Let (D;X) be a based diagram of a based graph (G; T) with g(D;X) = g(G; T). Constructs a compact connected orientable surface N(D;X) from (D;X) such that

(1) the surface N(D;X) is a union of a disk N in ℝ2 with the tree basis diagram X as a spine and attaching bands Bi (i = 1, 2, . . . , m) whose cores are the edges ai (i = 1, 2, . . . , m) of D,

(2) the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 is isomorphic to the ℤ2-intersection form on H1(N(D;X); ℤ2).

Because the nullity of the ℤ2-intersection form on H1(N(D;X); ℤ2) is equal to the number of the boundary components of the bounded surface N(D;X) minus one, the genus g(N(D;X)) is equal to the half of the ℤ2-rank of the ℤ2-form ɛ. This implies that

g(G;T)=g(D;X)=g(N(D;X))g(G).

Conversely, let F be a compact connected orientable surface containing G with genus g(F) = g(G), where F need not be closed. For any based graph (G; T), let N(G) be a regular neighborhood of G in F, which is obtained from a disk N in F with the tree basis T as a spine by attaching bands Bi (i = 1, 2, . . . , m) whose cores are the edges ai (i = 1, 2, . . . , m) of G. Then the inequality g(N(G)) ≤ g(F) holds. Let (D;X) be any based diagram of the based graph (G; T). Identify the disk N with a disk N(X) with the tree basis T as a spine. By construction, the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 is isomorphic to the ℤ2-intersection form on H1(N(G); ℤ2), which determines the genus g(N(G)) as the half of the ℤ2-rank of ɛ. Thus, the inequalities

g(G;T)g(D;X)=g(N(G))g(F)=g(G)

hold and we have g(G) = g(D; T) = g(G; T) for any based diagram (D;X) of (G; T).

The nullity ν(D;X) of (D;X) is the nullity of the ℤ2-form ɛ : ℤ2[D;X] × ℤ2[D;X] → ℤ2. The nullity ν(G; T) of a based graph (G; T) is the maximum of the nullity ν(D;X) for all based diagrams (D;X) of (G; T). Then the following corollary is obtained:

Corollary 2.3

The identity ν(G; T) = 1−χ(G)−2g(G) holds for any based graph (G, T).

This corollary shows that the nullity ν(G; T) is independent of a choice of tree bases T of G, and is therefore simply called the nullity of G and denoted by ν(G).

Proof

The graph G is obtained from the tree graph N(X;D) by attaching the mutually disjoint m-strings ai (i = 1, 2, . . . , m). Since the ℤ2-rank of ℤ2[D;X] is m by definition, we see from a calculation of the Euler characteristic χ(G) that χ(G) = 1+m−2m = 1−m. By the identity m = 2g(D;X)+ν(D;X) on the rank and the nullity of the ℤ2-form ɛ, the nullity ν(D;X) of a based diagram (D;X) of (G; T) is given by ν(D;X) = m−2g(D;X) = 1−χ(G) −2g(D;X). Hence we have

ν(G;T)=1-χ(G)-2g(G;T)=1-χ(G)-2g(G)

by Lemma 2.2.

The cross-index of a based diagram (D;X) is the non-negative integer ɛ(D;X) defined by

ɛ(D;X)=1i<jmɛ(ai,aj).

The following lemma is obtained:

Lemma 2.4

For every based diagram (D;X), the inequality ɛ(D;X) ≥ g(D;X) holds.

Proof

Let V be the ℤ2-matrix representing the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 with respect to the arc basis ai (i = 1, 2, . . . , m). Let ɛij = ɛ(ai, aj) be the (i, j)-entry of the matrix V. The ℤ2-rank r of the matrix V is equal to 2g(D;X) by definition. There are r column vectors in V that are ℤ2-linearly independent. By changing the indexes of the arc basis ai, we can find a sequence of integral pairs (ik, jk) (k = 1, 2, . . . , r) with 1 ≤ i1 < i2 · · · < irm and 1 ≤ j1 < j2 < · · · < jrm such that ɛikjk = 1 for all k (k = 1, 2, . . . , r). Here, note that this sequence (ik, jk) (k = 1, 2, . . . , r) may contain two pairs (ik, jk), (ik, jk) with kk′ and (ik, jk) = (jk, ik). By the identities ɛii = 0 and ɛij = ɛji for all i, j, we have

2ɛ(D;X)=1i,jmɛijk=1rɛikjk=r=2g(D;X).

Thus, the inequality ɛ(D;X) ≥ g(D;X) is obtained.

The cross-index ɛ(G; T) of a based graph (G; T) is the minimum of the cross-index ɛ(D;X) for all based diagrams (D;X) of (G; T). It may be used to compute the crossing number c(G; T) of a based graph (G; T) as it is stated in the following lemma:

Lemma 2.5

(Calculation Lemma) ɛ(G; T) = c(G; T) for every based graph (G; T).

Proof

Let ai (i = 1, 2, . . . , m) be an arc basis of a based diagram (D;X) of (G; T) attaching to the boundary of a regular neighborhood disk N of X in the plane.

By a homotopic deformation of ai into an embedded arc ai keeping the boundary points fixed, we construct a new based diagram (D′;X) of (G; T) with a basis ai(i=1,2,,,m) so that

(1) aiaj= if ɛ(ai, aj) = 0 and ij,

(2) ai and aj meet one point transversely if ɛ(ai, aj) = 1.

Then the cross-index ɛ(D;X) is equal to the crossing number c(D′;X) of the based diagram (D′;X) of (G; T). Hence the inequality ɛ(G; T) ≥ c(G; T) is obtained. Since ɛ(D;X) ≤ c(D;X) for every based graph (D;X) of (G; T), the inequality ɛ(G; T) ≤ c(G; T) holds. Hence the identity ɛ(G; T) = c(G; T) holds.

Calculation Lemma (Lemma 2.5) gives a computation method of the crossing number c(G; T) of a based graph (G; T) in a finite procedure.

In fact, let Xi (i = 1, 2, . . . , s) be all the tree basis diagrams of T in ℝ2. For every i, let (Dij,Xi) (j = 1, 2, . . . , ti) be a finite set of based diagrams of (G, T) such that every based diagram (D,Xi) of (G, T) coincides with a based diagram (Dij,Xi) for some j in a neighborhood of Xi. Then Calculation Lemma implies that the crossing number c(G; T) is equal to the minimum of the cross-indexes ɛ(Dij ;Xi) for all i, j.

The following corollary is obtained by a combination of Lemmas 2.2, 2.5 and definition and some observation.

Corollary 2.6

The inequalities

ɛ(G;T)=c(G;T)c(G)g(G)=g(G;T)

hold for every based graph (G; T).

Proof

The identity ɛ(G; T) = c(G; T) is given by Lemma 2.5. By definition, the inequality c(G; T) ≥ c(G) is given. To see that c(G) ≥ g(G), let D be a diagram of G with over-under information on the sphere S2 with c(D) = c(G). Put an upper arc around every crossing of D on a tube attaching to S2 to obtain a closed orientable surface of genus c(D) with G embedded (see Fig. 3).

Hence the inequality c(G) ≥ g(G) is obtained. The identity g(G) = g(G; T) is given by Lemma 2.2. (Incidentally, the inequality c(G; T) ≥ g(G; T) is directly obtained by Lemma 2.4.)

For an arbitrary tree T, the T-cross-index cT (G) of a connected graph G is the minimal number of c(G; T′) for all tree bases T′ of G such that T′ is homeomorphic to T if such a tree basis T′ of G exists. Otherwise, let cT (G) = ∞. The T-cross-index cT (G) is a topological invariant of a graph G associated to every tree T, whose computation is in principle simpler than a computation of the crossing number c(G) by Calculation Lemma (Lemma 2.5).

Let c*(G) be the family of the invariants cT (G) of a connected graph G for all trees T. The minimal value cmin(G) in the family c*(G) has appeared as the crossing number of a Γ-unknotted graph in the paper [3] on a spatial graph.

The finite maximal value cmax(G) in the family c*(G) is a well-defined invariant of a connected graph G, because there are only finitely many tree bases T in G. By definition, we have the following inequalities

cmax(G)cmin(G)c(G)g(G)

for every connected graph G. By definition, the following properties are mutually equivalent:

(i) G is a planar graph.

(ii) cmax(G) = 0.

(iii) cmin(G) = 0.

(iv) c(G) = 0.

(v) g(G) = 0.

Let Kn be the n-complete graph. Let n ≥ 5, because Kn is planar for n ≤ 4. To consider a tree basis T of Kn, the following lemma is useful:

Lemma 3.1

For any two isomorphic tree bases T and Tof Kn, there is an automorphism of Kn sending T to T. In particular, cT (Kn) = c(Kn; T) for every tree basis T of Kn.

Proof

Let Kn be the 1-skelton of the (n − 1)-simplex A = |v0v1 . . . vn−1|. The isomorphism f from T to T′ gives a permutation of the vertexes vi (i = 0, 1, 2, . . . , n−1) which is induced by a linear automorphism fA of the (n−1)-simplex A. The restriction of fA to the 1-skelton Kn of A is an automorphism of Kn sending T to T′.

A star-tree basis of Kn is a tree basis T* of Kn which is homeomorphic to a cone of n − 1 points to a single point. By Lemma 2.5 (Calculation Lemma), the crossing number c(Kn; T*) of the based graph (Kn; T*) is calculated as follows.

Lemma 3.2. c(Kn;T*)=(n-1)(n-2)(n-3)(n-4)24.1

Proof

Let Tn* denote the star-tree basis T* of Kn in this proof. Since K5 is non-planar, the computation c(K5;T5*)=1 is easily obtained (see Fig. 4). Suppose the calculation of c(Kn;Tn*) is done for n ≥ 5. To consider c(Kn+1;Tn+1*), let the tree basis Tn+1* be identified with the 1-skelton P1 of the stellar division of a regular convex n-gon P (in the plane) at the origin v0. Let vi (i = 1, 2, . . . , n) be the linearly enumerated vertexes of P1 in the boundary closed polygon ∂P of P in this order. We count the number of edges of (Kn+1;Tn+1*) added to (Kn:Tn*) contributing to the cross-index ɛ(Kn+1;Tn+1*). In the polygonal arcs of ∂P divided by the vertexes vn, v2, the vertex v1 and the vertexes v3, . . . , vn−1 construct pairs of edges contributing to the cross-index 1. In the polygonal arcs of ∂P divided by the vertexes vn, v3, the vertexes v1, v2 and the vertexes v4, . . . , vn−1 construct pairs of edges contributing to the cross-index 1. Continue this process. As the final step, in the polygonal arcs of ∂P divided by the vertexes vn, vn−2, the vertexes v1, v2, . . . , vn−3 and the vertex vn−1 construct pairs of edges contributing to the cross-index 1. By Calculation Lemma, we have

c(Kn+1;Tn+1*)-c(Kn;Tn*)=1(n-3)+2(n-4)++(n-3)(n-(n-1))=k=1n-3k(n-2-k)=(n-1)(n-2)(n-3)6,

so that

c(Kn+1;Tn+1*)=c(Kn;Tn*)+(n-1)(n-2)(n-3)6=(n-1)(n-2)(n-3)(n-4)24+(n-1)(n-2)(n-3)6=n(n-1)(n-2)(n-3)(n-4)24.

Thus, the desired identity on c(Kn;T*)=c(Kn;Tn*) is obtained.

For the crossing number c(Kn), R. K. Guy’s conjecture is known (see [2]):

Guy’s Conjecture

c(Kn) = Z(n) where

Z(n)=14n2   n-12   n-22   n-32,

where ⌊⌋ denotes the floor function.

Until now, this conjecture was confirmed to be true for n ≤ 12. In fact, Guy confirmed that it is true for n ≤ 10, and if it is true for any odd n, then it is also true for n + 1. S. Pan and P. B. Richter in [7] confirmed that it is true for n = 11, so that it is also true for n = 12. Thus,

c(Kn)=1   (n=5),3   (n=6),9   (n=7),18   (n=8),36   (n=9),60   (n=10),100   (n=11),150   (n=12).

It is further known by D. McQuillana, S. Panb, R. B. Richterc in [6] that c(K13) belongs to the set {219, 221, 223, 225} where 225 is the Guy’s conjecture.

Given a tree basis diagram X of a tree basis T of Kn, we can construct a based diagram (D;X) of (Kn; T) by Lemma 3.1, so that c(Kn; T) ≤ c(D;X).

To investigate cmin(K5) and cmax(K5), observe that the graph K5 has just 3 non-isomorphic tree bases, namely a linear-tree basis TL, a T-shaped-tree basis Ts and a star-tree basis T*, where the T-shaped-tree basis Ts is a graph constructed by two linear three-vertex graphs ℓ and ℓ′ by identifying the degree 2 vertex of ℓ with a degree one vertex of ℓ′. Since any of TL, Ts, T* is embedded in the planar diagram obtained from the diagram of K5 in Fig. 4 by removing the two crossing edges, we have c(K5; T) ≤ 1 for every tree basis T of K5. Since c(K5; T) ≥ c(K5) = 1,

c(K5)=cmin(K5)=cmax(K5)=1.

To investigate cmin(K6) and cmax(K6), observe that K6 has just 6 non-isomorphic tree bases (see Fig. 5). In Appendix, it is shown how the non-isomorphic tree bases are tabulated in case of the complete graph K11. For every tree basis T in Fig. 5, we can construct a based diagram (D;X) of (K6, T) with c(D;X) ≤ 5 by Lemma 3.1. Thus, by c(K6) = 3 and c(K6; T*) = 5 and c(K6; TL) ≤ 3 for a linear-tree basis TL of K6 (see Fig. 6), we have

c(K6)=cmin(K6)=c(K6;TL)=3<c(K6;T*)=cmax(K6)=5.

In particular, this means that cmax(G) is different from c(G) for a general connected graph G. It is observed in [2] that

c(Kn)14·n2·n-12·n-22·n-32=n(n-1)(n-2)(n-3)64.

More precisely, it is observed in [7] that

0.8594Z(n)c(Kn)Z(n).

By Lemma 3.2, we have

cmax(Kn)c(Kn;T*)=(n-1)(n-2)(n-3)(n-4)24

Hence the difference cmax(Kn) − c(Kn) is estimated as follows:

cmax(Kn)-c(Kn)(n-1)(n-2)(n-3)(n-4)24-n(n-1)(n-2)(n-3)64=(n-1)(n-2)(n-3)(5n-32)192.

Hence we have

limn+(cmax(Kn)-c(Kn))=limn+cmax(Kn)=+.

As another estimation, we have

0<c(Kn)cmax(Kn)24(n-1)(n-2)(n-3)(n-4)·n(n-1)(n-2)(n-3)64=38·nn-4,

so that for n ≥ 16

0<c(Kn)cmax(Kn)12.

Thus, we have the following lemma, which is used in § 4:

Lemma 3.3

limn+(cmax(Kn)-c(Kn))=limn+cmax(Kn)=+,0<c(Kn)cmax(Kn)12         (n16).

Here is a question on a relationship between the crossing number and the minimally based crossing number.

Question (open)

c(G) = cmin(G) for every connected graph G ?

The authors confirmed that

c(Kn)=c(Kn;TL)=cmin(Kn)

for n ≤ 12, where TL is a linear-tree basis of Kn. The diagrams with minimal cross-index for K11 and K12 are given in Fig. 7 and Fig. 8, respectively. It is noted that if this question is yes for K13, then the crossing number c(K13) would be computable with use of a computer. If this question is no, then the T-cross-index cT (G) would be more or less a new invariant for every tree T. Some related questions on the cross-index of Kn remain also open. Is there a linear-tree basis TL in Kn with c(Kn; TL) = cmin(Kn) for every n ≥ 13 ? Furthermore, is the linear-tree basis TL extendable to a Hamiltonian loop without crossing ?

Quite recently, a research group of the second and third authors confirmed in [1] that

c(Kn;TL)=Z(n)

for all n.

The genus g(Kn) of Kn is known by G. Ringel and J. W. T. Youngs in [8] to be

g(Kn)=(n-3)(n-4)12=1   (n=5,6,7),   2(n=8),   3(n=9),   4(n=10),   5(n=11),   6(n=12),   ,

where ⌈⌉ denotes the ceiling function. Then the nullity ν(Kn) of Kn is computed as follows:

ν(Kn)=1-χ(Kn)-2g(Kn)=(n-1)(n-2)/2-2(n-3)(n-4)12=4(n=5),   8(n=6),   13(n=7),   17(n=8),   22(n=9),   28(n=10),   35(n=11),   43(n=12),.

In this section, we show that the invariant c*(G) is more or less a new invariant. For this purpose, for a real-valued invariant I(G) of a connected graph G which is not bounded when G goes over the range of all connected graphs, a virtualized invariant Ĩ(G) of G is defined to be Ĩ(G) = f(I(G)) for a fixed non-constant real polynomial f(x) in x. Every time a different non-constant polynomial f(t) is given, a different virtualized invariant Ĩ(G) is obtained from the invariant I(G). The following theorem is the main result of this paper showing a certain independence between the cross-index c*(G) and the other invariants c(G), g(G), χ(G).

Theorem 4.1

Let c̃max(G), (G), (G), χ̃(G) be any virtualized invariants of the invariants cmax(G), c(G), g(G), χ(G), respectively. Every linear combination of the invariants c̃max(G), (G), (G), χ̃(G) in real coefficients including a non-zero number is not bounded when G goes over the range of all connected graphs.

Let N(vG) be the regular neighborhood of the vertex set vG in G. A connected graph G is vertex-congruent to a connected graph G′ if there is a homeomorphism N(vG) ≅ N(vG). Then we have the same Euler characteristic: χ(G) = χ(G′).

To show this theorem, the following lemma is used.

Lemma 4.2

(1) For every n > 1, there are vertex-congruent connected graphs Gi (i = 0, 1, 2, . . . , n) such thatcmax(Gi)=c(Gi)=g(Gi)=i

for all i.

(2) For every n > 1, there are connected graphs Hi (i = 1, 2, . . . , n) such thatcmax(Hi)=c(Hi)=i         and         g(Hi)=1

for all i.

Proof

Use the based diagram (D5;X) of K5 in Fig. 4 with c(D5;X) = c(K5; T*) = g(K5) = 1. Let D50 be the planar diagram without crossing by obtained from D5 by smoothing the crossing, illustrated in Fig. 9. Let K50 be the planar graph given by D50. For the proof of (1), let G0 be the connected graph obtained from the n copies of K50 by joining n − 1 edges one after another linearly by introducing them (see Fig. 10).

Let Gi (i = 1, 2, . . . , n) be the connected graphs obtained from G0 by replacing the first i copies of K50 with the i copies of K5 (see Fig. 11 for i = 2). Since c(K5; T) = 1 for every tree basis T and every tree basis Ti of Gi is obtained from the i tree bases of K5 and the ni tree bases of K50 by joining the n − 1 edges one after another linearly. Then g(Gi) ≤ cTi (Gi) ≤ i for every i. By Genus Lemma and Calculation Lemma, we obtain g(Gi) = g(Gi; Ti) ≥ i so that

g(Gi)=c(Gi)=cmax(Gi)=i

for all i, showing (1). For (2), let Hi be the graph obtained from K5 by replacing every edge except one edge by i multiple edges with |vHi| = |vK5| = 5. Then g(Hi) = g(K5) = 1. Note that every tree basis T of Hi is homeomorphic to a tree basis of K5. Then the identity cmax(K5) = 1 implies cmax(Hi) ≤ i. Since Hi contains i distinct K5-graphs with completely distinct edges except common one edge. Then we have c(Hi) ≥ i and hence

cmax(Hi)=c(Hi)=i         and         g(Hi)=1

for all i.

By using Lemma 4.2, the proof of Theorem 4.1 is given as follows:

Proof of Theorem 4.1

Let

c˜max(G)=f1(cmax(G)),c˜(G)=f2(c(G)),g˜(G)=f3(g(G)),χ˜(G)=f4(χ(G))

for non-constant real polynomials fi(x) (i = 1, 2, 3, 4). Suppose that the absolute value of a linear combination

a1c˜max(G)+a2c˜(G)+a3g˜(G)+a4χ˜(G)

with real coefficients ai (i = 1, 2, 3, 4) is smaller than or equal to a positive constant a for all connected graphs G. Then it is sufficient to show that a1 = a2 = a3 = a4 = 0. If G is taken to be a planar graph, then cmax(G) = c(G) = g(G) = 0. There is an infinite family of connected planar graphs whose Euler characteristic family is not bounded. Hence the polynomial a4f4(x) is a constant polynomial in x. Since f4(x) is a non-constant polynomial in x, we must have a4 = 0. Then the inequality

a1c˜max(G)+a2c˜(G)+a3g˜(G)a

holds. By Lemma 4.2 (1), the polynomial a1f1(x) + a2f2(x) + a3f3(x) in x must be a constant polynomial. By Lemma 4.2 (2), the polynomial a1f1(x) + a2f2(x) in x must be a constant polynomial. These two claims mean that the polynomial a3f3(x) is a constant polynomial in x, so that a3 = 0 since f3(x) is a non-constant polynomial. Let a′ = a1f1(x) + a2f2(x) which is a constant polynomial in x. Then

a1c˜max(G)+a2c˜(G)=a1(f1(cmax(G))-f1(c(G))+a,

so that

a1(f1(cmax(G))-f1(c(G))+aa

for all connected graphs G. By Lemma 3.3, we have

limn+(cmax(Kn)-c(Kn))=limn+cmax(Kn)=+,0<c(Kn)cmax(Kn)12         (n16).

Let d and e be the highest degree and the highest degree coefficient of the polynomial f1(t). Then we have

limn+f1(cmax(Kn))-f1(c(Kn))=limn+|ecmax(Kn)d(1-(c(Kn)cmax(Kn))d)|=+.

Thus, we must have a1 = 0, so that a1 = a2 = a3 = a4 = 0.

In this appendix, it is shown how the non-isomorphic tree bases are tabulated in case of the complete graph K11. This tabulation method is important to compute the T-cross index cT (Kn) for a tree basis T of Kn, which is equal to the cross-index c(Kn; T) by Lemma 3.1.

Our tabulation method is based on a formula on the numbers of vertexes with respect to degrees. Let T be a tree on the 2-sphere, and vi the number of vertexes of T of degree i. Then the number V of the vertexes of T is the sum of all vis for i = 1, 2, . . . ;

V=v1+v2++vi+.

Since there are i edges around every vertex of degree i and each edge has two end points, the total number E of edges of T is as follows:

E=12(v1+2v2+3v3++ivi+).

Since T is a tree, the number F of faces of T is 1. Then the following formula is obtained from the Euler characteristic of the 2-sphere VE + F = 2:

v1=2+v3+2v4++(i-2)vi+.

Let V = 11, i.e., let T be a tree basis of K11. Since E = 10 by the Euler characteristic, the following equality holds:

12(v1+2v2+3v3++10v10)=10.

From the equalities (5.1) and (5.2), the following formula is obtained:

v2+2v3+3v4++(i-1)vi++9v10=9.

In Table 1, all the possible combinations of vis which satisfy V = 11 and the formula (5.3) are listed. In Fig. 12, all the graphs in Table 1 are shown, where degree-two vertexes are omitted for simplicity. By giving vertexes with degree two to each graph in Fig. 12, all the tree bases of K11 are obtained as shown in Figs. 13, 14, 15 and 16.

  1. Y. Gokan, H. Katsumata, K. Nakajima, A. Shimizu, and Y. Yaguchi. A note on the cross-index of a complete graph based on a linear tree. J Knot Theory Ramifications., 27(2018), 24 pp.
    CrossRef
  2. RK. Guy. Crossing numbers of graphs. Graph Theory and Applications, 303, Springer, Berlin, 1972:111-124. Lecture Notes in Math.
    CrossRef
  3. A. Kawauchi. On transforming a spatial graph into a plane graph. Progress Theor Phys Suppl., 191(2011), 225-234.
    CrossRef
  4. A. Kawauchi. Knot theory for spatial graphs attached to a surface. Knot Theory and its Applications, 670, Amer. Math. Soc, Providence, RI, 2016:141-169. Contemp. Math.
    CrossRef
  5. A. Kawauchi. Complexities of a knitting pattern. Reactive and Functional Polymers., 131(2018), 230-236.
    CrossRef
  6. D. McQuillan, S. Pan, and RB. Richter. On the crossing number of K13. J Comb Theory, Ser B., 115(2015), 224-235.
    CrossRef
  7. S. Pan, and PB. Richter. The Crossing number of K11 is 100. J Graph Theory., 56(2007), 128-134.
    CrossRef
  8. G. Ringel, and JWT. Youngs. Solution of the Heawood Map-Coloring Problem. Proc Nat Acad Sci USA., 60(1968), 438-445.
    Pubmed KoreaMed CrossRef