SAS Journals

Scientific Journals and Yearbooks Published at SAS

Article List

Tatra Mountains Mathematical Publications

Volume 9, 1996, No. 3

Content:

Erdős, P.
Some of my favourite problems on cycles and colorings.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 7-9.
Borodin, O.
More about the weight of edges in planar graph.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 11-14.
Schiermeyer, I.
Fast exact colouring algorithms.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 15-30.
Broersma, H. - Ryjacek, Z. - Schiermeyer, I.
Unifying results on Hamiltonian claw-free graphs.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 31-39.
Owens, P.
Shortness exponents for some families of maximal planar graphs.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 41-50.
Klesc, M.
The crossing number of $K_2,3× P_n$ and $K_2,3× S_n$.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 51-56.
Balińska, K. - Quintas, L.
Isomorphism classes of one edge transformed graphs.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 57-67.
Tuza, Z. - Voigt, M.
On a conjecture of Erdős, Rubin and Taylor.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 69-82.
Broere, I. - Jonck, E. - Voigt, M.
The induced path number of a complete multipartite graph.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 83-88.
Miller, M.
Some open problems in optimal digraphs.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 89-96.
Böhme, T. - Harant, J. - Tkac, M.
On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 97-102.
Voss, H.
Problem.
In Tatra Mountains Mathematical Publications. Vol. 9, no. 3 (1996), p. 103-104.

Some of my favourite problems on cycles and colorings
Paul Erdős ¹⁾

1)	Mathematical Institute, Hungarian Academy of Sciences; Realtanoda u. 13-15; H-1053 Budapest; HUNGARY.

Six problems concerning graph cycles and colourings are presented.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 7-9.

More about the weight of edges in planar graph
Oleg Borodin ¹⁾

1)	Institute of Mathematics, Siberian Branch of Russian Academy of Sciences; Novosibirsk, 630090; RUSSIA.

The weight of an edge in a plane graph is the degree sum of its end vertices. Recent results on the minimum weight of all edges, denoted by $w$, of those incident with a triangle, $w^*$, and those incident with two triangles, $w^*\ast$, in a plane graph are discussed. It is proved that if a normal plane map has $w^*\ast=∞$, then either $w^*≤ 9$ or $w≤ 8$, where both bounds are sharp.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 11-14.

Fast exact colouring algorithms
Ingo Schiermeyer ¹⁾

1)	RWTH Aachen, Department C of Mathematics; Templergraben 55; D-52056 Aachen; GERMANY.

In this paper we describe and analyze four improved algorithms for deciding the $3-, 4-, 5-$ and $6-$ Colourability problem. If $G$ is a simple graph on $n$ vertices then we will show that these algorithms test a graph for $3-, 4-, 5-$ or $6$-Colourability, i.e., an assignment of three, four, five or six colours to the vertices of $G$ such that two adjacent vertices obtain different colours, in less than $O(1,398^N)$, $O(1,585ⁿ)$, $O(1,938ⁿ)$ or $O(2,155ⁿ)$ steps.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 15-30.

Unifying results on Hamiltonian claw-free graphs
Hajo J. Broersma ¹⁾, Zdeněk Ryjacek ²⁾, Ingo Schiermeyer ³⁾

1)	Faculty of Mathematical Sciences, University of Twente; P.O.Box 217; 7500 AE Enschede; NETHERLAND.
2)	Katedra matematiky, Zapadoceska univerzita; Univerzitni 22; 306 14 Plzen; CZ.
3)	RWTH Aachen, Department C of Mathematics; Templergraben 55; D-52056 Aachen; GERMANY.

This work was motivated by many (recent) papers on hamiltonicity of claw-free graphs, i.e., graphs that do not contain $K_1,3$ as an induced subgraph. By combining ideas from these papers with some new observations, we unify several of the existing sufficiency results, using a new sufficient condition consisting of seven subconditions. If each pair of vertices at distance two of a 2-connected claw-free graph $G$ satisfies at least one of these subconditions, then $G$ is Hamiltonian. We also present infinite classes of examples of graphs showing that these subconditions are, in some sense, independent.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 31-39.

Shortness exponents for some families of maximal planar graphs
Peter John Owens ¹⁾

1)	Department of Mathematics and Statistics, University of Surrey; Guildford GU2 5XH; U. K..

It is shown that the family of maximal planar simple graphs such that every vertex has valency 5 or $q≥ 14$, not only has non-Hamiltonian members but even has a shortness exponent less than one.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 41-50.

The crossing number of $K_2,3× P_n$ and $K_2,3× S_n$
Marian Klesc ¹⁾

1)	Katedra matematiky FEI TU, Hlavna 6, 042 00 Kosice, Slovakia. marian.klesc@tuke.sk

There are several known exact results on the crossing number of Cartesian product of paths or cycles with ``small'' graphs. Here we determine the crossing number of $K_2,3× P_n$ and $K_2,3× S_n$ where $P_n$ and $S_n$ are the path and the star with $n$ edges, respectively.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 51-56.

Isomorphism classes of one edge transformed graphs
Krystyna T. Balińska ¹⁾, Louis V. Quintas ²⁾

1)	Computer Science Center, Technical University of Poznań; Pl. M. Sklodowskej-Curie 5; 60-965 Poznań; POLAND.
2)	Mathematics Department, Pace University; New York, NY 10038; U. S. A..

The isomorphism classes and the chromatic numbers of the one edge deleted subgraphs and the one edge extended supergraphs of a graph are studied. Graphs are determined having the property that either every one edge deleted subgraph or every one edge extended supergraph is isomorphically distinct. The following is one of a number of open problems considered. For a given chromatic number $χ₀$, characterize the class of graphs $\langle G\rangle$ such that $χ(G)=χ₀$ and every one edge extended supergraph of $G$ has chromatic number $χ₀$. Similarly, characterize the class of graphs $\langle H\rangle$ such that $χ(H)=χ₀$ and every one edge extended supergraph of $H$ has chromatic number $χ₀+1$.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 57-67.

On a conjecture of Erdős, Rubin and Taylor
Zsolt Tuza ¹⁾, Margit Voigt ²⁾

1)	Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17; H-1111 Budapest; HUNGARY. tuza@lutra.sztaki.hu
2)	Institut für Mathematik, Technische Universitat Ilmenau; D-98684 Ilmenau; GERMANY.

A graph $G$ with vertex set $V$ and edge set $E$ is called $(a, b)$-choosable if for any assignment of lists $L(v)$ of colours to the vertices $v$ of $G$ with $|L(v)|=a$ it is possible to choose subsets $C(v)\subset L(v)$, $|C(v)|=b$ for every $v\in V$ such that $C(u)\cap C(v)=\emptyset$ for all $uv\in E$. In 1979, Erdős, Rubin and Taylor [P. Erdős, A. L. Rubin, H. Taylor: Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics Graph Theory and Computing, Arcata, California, 1979, Congressus Numeratium 26 (1979), 125–157] raised the conjecture that every $(a, b)$-choosable graph $G$ is also $(am, bm)$-choosable for all $m>1$. We investigate the case $b=1$, presenting some classes of $(a, 1)$-choosable graphs for which $(am,m)$-choosability can be proved for all $m$.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 69-82.

The induced path number of a complete multipartite graph
Izak Broere ¹⁾, Elizabeth Jonck ²⁾, Margit Voigt ³⁾

1)	Department of Mathematics, Rand Afrikaans University; P.O.Box 524; Auckland Paark; 2006 SOUTH AFRICA.
2)	Department of Mathematics, Rand Afrikaans University; P. O. Box 524; Auckland Park; 2006 SOUTH AFRICA.
3)	Institut für Mathematik, Technische Universitat Ilmenau; D-98684 Ilmenau; GERMANY.

The induced path number $ρ(G)$ of a graph $G$ is defined as the minimum number of subsets into which the vertex set of $G$ can be partitioned so that each subset induces a path. In this paper we determine the induced path number of a complete $l$-partite graph.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 83-88.

Some open problems in optimal digraphs
Mirka Miller ¹⁾

1)	Department of Computer Science, The University of Newcastle; NSW 2308 AUSTRALIA.

The Moore bound for a digraph of maximum out-degree $d$ and diameter $k$ is $M_{d, k}=1+d+…+d^k$. It is known that digraphs of order $M_{d, k}$ do not exist for $d>1$ and $k>1$. This being the case, for $d>1$ and $k>1$, we consider digraphs which are `close' to Moore, that is, digraphs with maximum out-degree $d≥ 2$, diameter $k≥ 2$ and order $n(d, k)=M_{d, k}-Δ_{d, k}$ where $Δ_{d, k}$ is the minimum possible `defect' for given $d$ and $k$. Furthermore, we consider the construction of diregular digraphs with minimum diameter, given the order and degree. At the end of each section we present a number of open problems.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 89-96.

On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs
Thomas Böhme ¹⁾, Jochen Harant ²⁾, Michal Tkac ³⁾

1)	Institut Für Mathematik, TU Ilmenau; PF 327,G-98684 Ilmenau; Germany.
2)	Institute of Mathematics, Technical University Ilmenau; Postfach 327; D-98684 Ilmenau; GERMANY.
3)	Strojnicka fakulta TU, Letna 9; 040 00 Kosice.

A well known theorem of H. Whitney states that every maximal planar graph without separating 3-cycles is Hamiltonian. The problem discussed here is how many separating 3-cycles such a graph must have to be non-Hamiltonian.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 97-102.

Problem
Heinz-Jürgen Voss ¹⁾

1)	Technische Universitat Dresden, Abteilung Mathematik; Institut für Algebra; Mommsenstrasse 13; 01062 Dresden; GERMANY.

Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 103-104.