### 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

### Abstract

For every tree

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

### 1. Introduction

A _{2}-form

on (

are established. In particular, it turns out that the crossing number

For a tree ^{T}

Define ^{T}^{T}

Let ^{*}(^{T}^{min}(^{*}(^{min}(

The finite maximal value ^{max}(^{*}(

for every connected graph

(i)

(ii) ^{max}(

(iii) ^{min}(

(iv)

(v)

In § 3, the case of the _{n}_{n}^{min}(_{5}) = ^{max}(_{5}) and ^{min}(_{n}^{max}(_{n}^{min}(^{max}(

The main purpose of this paper is to show that the family ^{*}(^{*}(

### Theorem 4.1

^{max}^{max}^{max}

The proof of this theorem is given in § 4.

As an _{11}. This tabulation method is important to compute the ^{T}_{n}_{n}^{T}_{n}_{n}

### 2. The Cross-index of a Graph associated to a Tree

By a _{11} and _{12} without degree 4 vertexes. A

### Lemma 2.1

^{3},

**Proof**

In any spatial graph diagram ^{2}) of ^{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 (

The crossing number ^{2}) be a regular neighborhood of _{i}^{2}^{2}) where ^{2} = ℝ^{2}∪{∞} denotes the 2-sphere which is the one-point compactification of the plane ℝ^{2}.

Let ℤ_{2}[_{2} vector space with the arcs _{i}_{2}-basis. For any two arcs _{i}_{j}_{i}_{j}_{j}_{j}_{i}_{i}_{j}_{i}_{j}_{2}-form

called the ℤ_{2}-_{2}-rank of the ℤ_{2}-form _{2}[_{2}[_{2}, which is seen to be even since the ℤ_{2}-form _{2}-symplectic form.

The

### Lemma 2.2

(Genus Lemma)

**Proof**

Let (

(1) the surface ^{2} with the tree basis diagram _{i}_{i}

(2) the ℤ_{2}-form _{2}[_{2}[_{2} is isomorphic to the ℤ_{2}-intersection form on _{1}(_{2}).

Because the nullity of the ℤ_{2}-intersection form on _{1}(_{2}) is equal to the number of the boundary components of the bounded surface _{2}-rank of the ℤ_{2}-form

Conversely, let _{i}_{i}_{2}-form _{2}[_{2}[_{2} is isomorphic to the ℤ_{2}-intersection form on _{1}(_{2}), which determines the genus _{2}-rank of

hold and we have

The _{2}-form _{2}[_{2}[_{2}. The

### Corollary 2.3

This corollary shows that the nullity

**Proof**

The graph _{i}_{2}-rank of ℤ_{2}[_{2}-form

by Lemma 2.2.

The

The following lemma is obtained:

### Lemma 2.4

**Proof**

Let _{2}-matrix representing the ℤ_{2}-form _{2}[_{2}[_{2} with respect to the arc basis _{i}_{ij}_{i}_{j}_{2}-rank _{2}-linearly independent. By changing the indexes of the arc basis _{i}_{k}_{k}_{1} < _{2} · · · < _{r}_{1} < _{2} < · · · < _{r}_{ikjk} = 1 for all _{k}_{k}_{k}_{k}_{k}_{′}, _{k}_{′}) with _{k}_{k}_{k}_{′}, _{k}_{′}). By the identities _{ii}_{ij}_{ji}

Thus, the inequality

The

### Lemma 2.5

(Calculation Lemma)

**Proof**

Let _{i}

By a homotopic deformation of _{i}

(1) _{i}_{j}

(2) _{i}_{j}

Then the cross-index

Calculation Lemma (Lemma 2.5) gives a computation method of the crossing number

In fact, let _{i}^{2}. For every _{ij}_{i}_{i}_{i}_{ij}_{i}_{i}_{ij}_{i}

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

### Corollary 2.6

**Proof**

The identity ^{2} with ^{2} to obtain a closed orientable surface of genus

Hence the inequality

For an arbitrary tree ^{T}^{T}^{T}

Let ^{*}(^{T}^{min}(^{*}(

The finite maximal value ^{max}(^{*}(

for every connected graph

(i)

(ii) ^{max}(

(iii) ^{min}(

(iv)

(v)

### 3. The Invariants of a Complete Graph

Let _{n}_{n}_{n}

### Lemma 3.1

_{n}_{n}^{T}_{n}_{n}_{n}

**Proof**

Let _{n}_{0}_{1} . . . _{n}_{−1}|. The isomorphism _{i}_{A}_{A}_{n}_{n}

A _{n}^{*} of _{n}_{n}^{*}) of the based graph (_{n}^{*}) is calculated as follows.

### Lemma 3.2. $c({K}_{n};{T}^{*})=\frac{(n-1)(n-2)(n-3)(n-4)}{24}$ .1

**Proof**

Let ^{*} of _{n}_{5} is non-planar, the computation ^{1} of the stellar division of a regular convex _{0}. Let _{i}^{1} in the boundary closed polygon _{n}_{2}, the vertex _{1} and the vertexes _{3}, . . . , _{n}_{−1} construct pairs of edges contributing to the cross-index 1. In the polygonal arcs of _{n}_{3}, the vertexes _{1}, _{2} and the vertexes _{4}, . . . , _{n}_{−1} construct pairs of edges contributing to the cross-index 1. Continue this process. As the final step, in the polygonal arcs of _{n}_{n}_{−2}, the vertexes _{1}, _{2}, . . . , _{n}_{−3} and the vertex _{n}_{−1} construct pairs of edges contributing to the cross-index 1. By Calculation Lemma, we have

so that

Thus, the desired identity on

For the crossing number _{n}

**Guy’s Conjecture**

_{n}

Until now, this conjecture was confirmed to be true for

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

Given a tree basis diagram _{n}_{n}_{n}

To investigate ^{min}(_{5}) and ^{max}(_{5}), observe that the graph _{5} has just 3 non-isomorphic tree bases, namely a linear-tree basis ^{L}^{s}^{*}, where the ^{s}^{L}^{s}^{*} is embedded in the planar diagram obtained from the diagram of _{5} in Fig. 4 by removing the two crossing edges, we have _{5}; _{5}. Since _{5}; _{5}) = 1,

To investigate ^{min}(_{6}) and ^{max}(_{6}), observe that _{6} has just 6 non-isomorphic tree bases (see Fig. 5). In _{11}. For every tree basis _{6}, _{6}) = 3 and _{6}; ^{*}) = 5 and _{6}; ^{L}^{L}_{6} (see Fig. 6), we have

In particular, this means that ^{max}(

More precisely, it is observed in [7] that

By Lemma 3.2, we have

Hence the difference ^{max}(_{n}_{n}

Hence we have

As another estimation, we have

so that for

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

### Lemma 3.3

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

**Question (open)**

^{min}

The authors confirmed that

for ^{L}_{n}_{11} and _{12} are given in Fig. 7 and Fig. 8, respectively. It is noted that if this question is yes for _{13}, then the crossing number _{13}) would be computable with use of a computer. If this question is no, then the ^{T}_{n}^{L}_{n}_{n}^{L}^{min}(_{n}^{L}

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

for all

The genus _{n}_{n}

where ⌈⌉ denotes the ceiling function. Then the nullity _{n}_{n}

### 4. Independence of the Cross-index

In this section, we show that the invariant ^{*}(^{*}(

### Theorem 4.1

^{max}^{max}^{max}

Let _{G}_{G}_{G}_{G}_{′}). Then we have the same Euler characteristic:

To show this theorem, the following lemma is used.

### Lemma 4.2

(1) ^{i}

(2) ^{i}

**Proof**

Use the based diagram (_{5};_{5} in Fig. 4 with _{5};_{5}; ^{*}) = _{5}) = 1. Let _{5} by smoothing the crossing, illustrated in Fig. 9. Let ^{0} be the connected graph obtained from the

Let ^{i}^{0} by replacing the first _{5} (see Fig. 11 for _{5}; ^{i}^{i}_{5} and the ^{i}^{Ti} (^{i}^{i}^{i}^{i}

for all ^{i}_{5} by replacing every edge except one edge by _{Hi}| = |_{K}_{5}| = 5. Then ^{i}_{5}) = 1. Note that every tree basis ^{i}_{5}. Then the identity ^{max}(_{5}) = 1 implies ^{max}(^{i}^{i}_{5}-graphs with completely distinct edges except common one edge. Then we have ^{i}

for all

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

**Proof of Theorem 4.1**

Let

for non-constant real polynomials _{i}

with real coefficients _{i}_{1} = _{2} = _{3} = _{4} = 0. If ^{max}(_{4}_{4}(_{4}(_{4} = 0. Then the inequality

holds. By Lemma 4.2 (1), the polynomial _{1}_{1}(_{2}_{2}(_{3}_{3}(_{1}_{1}(_{2}_{2}(_{3}_{3}(_{3} = 0 since _{3}(_{1}_{1}(_{2}_{2}(

so that

for all connected graphs

Let _{1}(

Thus, we must have _{1} = 0, so that _{1} = _{2} = _{3} = _{4} = 0.

### 5. Appendix: Tabulation of the Tree Bases of K _{11}

In this appendix, it is shown how the non-isomorphic tree bases are tabulated in case of the complete graph _{11}. This tabulation method is important to compute the ^{T}_{n}_{n}_{n}

Our tabulation method is based on a formula on the numbers of vertexes with respect to degrees. Let _{i}_{i}

Since there are

Since

Let _{11}. Since

From the equalities (

In Table 1, all the possible combinations of _{i}_{11} are obtained as shown in Figs. 13, 14, 15 and 16.

### Figures

### Tables

case | _{1} | _{2} | _{3} | _{4} | _{5} | _{6} | _{7} | _{8} | _{9} | _{10} |
---|---|---|---|---|---|---|---|---|---|---|

A | 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |

B | 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

C | 8 | 2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |

D | 9 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |

E | 7 | 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |

F | 8 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |

G | 9 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |

H | 9 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |

I | 8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |

J | 8 | 0 | 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |

K | 7 | 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |

L | 6 | 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |

M | 8 | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |

N | 8 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

O | 7 | 2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

P | 7 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

Q | 6 | 3 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

R | 5 | 5 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

S | 8 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |

T | 7 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |

U | 6 | 3 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |

V | 7 | 0 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

W | 6 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

X | 5 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

Y | 4 | 6 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

Z | 6 | 1 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

5 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |

4 | 5 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |

3 | 7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |

2 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

### References

- 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. - RK. Guy.
Crossing numbers of graphs . Graph Theory and Applications,303 , Springer, Berlin, 1972:111-124. Lecture Notes in Math. - A. Kawauchi.
On transforming a spatial graph into a plane graph . Progress Theor Phys Suppl.,191 (2011), 225-234. - 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. - A. Kawauchi.
Complexities of a knitting pattern . Reactive and Functional Polymers.,131 (2018), 230-236. - D. McQuillan, S. Pan, and RB. Richter.
On the crossing number of K . J Comb Theory, Ser B.,_{13}115 (2015), 224-235. - S. Pan, and PB. Richter.
The Crossing number of K . J Graph Theory.,_{11}is 10056 (2007), 128-134. - G. Ringel, and JWT. Youngs.
Solution of the Heawood Map-Coloring Problem . Proc Nat Acad Sci USA.,60 (1968), 438-445.