Search

Abstract: In this article a complete classification of tetravalent arc-transitive graphs of order twice a product of two primes is given. [Copyright &y& Elsevier]

Abstract: A graph is said to be -prime if, whenever it is a subgraph of a nontrivial Cartesian product graph, it is a subgraph of one of the factors. A diagonalized Cartesian product is obtained from a Cartesian product graph by connecting two vertices of maximal distance by an additional edge. We show there that a diagonalized product of -prime graphs is again -prime. Klavžar et al. [S. Klavžar, A. Lipovec, M. Petkovšek, On subgraphs of Cartesian product graphs, Discrete Math. 244 (2002) 223–230] proved that a graph is -prime if and only if it admits a nontrivial path--coloring. We derive here a characterization of all path--colorings of Cartesian products of -prime graphs. [Copyright &y& Elsevier]

Abstract: A regular edge-transitive graph is said to be semisymmetric if it is not vertex-transitive. By Folkman [J. Folkman, Regular line-symmetric graphs, J. Combin Theory 3 (1967) 215–232], there is no semisymmetric graph of order or for a prime and by Malnič, et al. [A. Malnič, D. Marušič, C.Q. Wang, Cubic edge-transitive graphs of order , Discrete Math. 274 (2004) 187–198], there exists a unique cubic semisymmetric graph of order , the so-called Gray graph of order 54. In this paper it is shown that a connected cubic semisymmetric graph of order exists if and only if is divisible by 3. There are exactly two such graphs for a given order, which are constructed explicitly. [Copyright &y& Elsevier]

Abstract: We prove a theorem that for an integer , if is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of , where , is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least , , nonisomorphic nonorientable triangular embeddings of for , . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given. [Copyright &y& Elsevier]