✦ LIBER ✦

On Hamiltonicity of Vertex-Transitive Graphs and Digraphs of Orderp4

✍ Scribed by Yu Qing Chen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 352 KB
Volume: 72
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1796

No coin nor oath required. For personal study only.

✦ Synopsis

The main result of this paper is that vertex-transitive graphs and digraphs of order p 4 are Hamiltonian, where p is a prime number. 1998 Academic Press 1. INTRODUCTION Witte [7] proved that Cayley digraphs of finite p-groups are Hamiltonian. In [2], Marus$ ic$ showed that all vertex-transitive digraphs of order p k with k 3 are Cayley digraphs. The examples of non-Cayley vertex-transitive graphs of order p k for k 4 can be found in [3]. In this paper, we prove Main Result. Vertex-transitive graphs and digraphs of order p 4 are Hamiltonian, where p is a prime.

The remainder of this paper is organized as follows: in Section 1, we recall some basic facts in group theory; in Section 2, we discuss the presentations of vertex-transitive graphs and digraphs by using their automorphism groups; in Section 3, we prove the main result. We will reserve p to denote a prime number throughout this paper.

The author thanks Professor H. Glover for his guidance and encouragement. The author also thanks the referees for their suggestions and comments.

1. PRELIMINARIES IN GROUP THEORY

In this section, we fix some notations and review some basic results in group theory. For the proofs of these results see [4 6].

📜 SIMILAR VOLUMES

On the Edge Connectivity, Hamiltonicity,

On the Edge Connectivity, Hamiltonicity, and Toughness of Vertex-Transitive Graphs

✍ Jan van den Heuvel; Bill Jackson 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let G be a connected k-regular vertex-transitive graph on n vertices. For S V(G) let d(S) denote the number of edges between S and V(G)"S. We extend results of Mader and Tindell by showing that if d(S)< 2 9 (k+1) 2 for some S V(G) with 1 3 (k+1) |S| 1 2 n, then G has a factor F such that GÂE(F ) is

Tetravalent vertex-transitive graphs of

Tetravalent vertex-transitive graphs of order 4p

✍ Jin-Xin Zhou 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

A graph is __vertex‐transitive__ if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a __Cayley graph__ if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs

A class of self-complementary vertex-tra

A class of self-complementary vertex-transitive digraphs

✍ Gek-Ling Chia; Chong-Keang Lim 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) selfcomplementary ver

Cubic vertex-transitive graphs of order

Cubic vertex-transitive graphs of order 2pq

✍ Jin-Xin Zhou; Yan-Quan Feng 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

A graph is vertex-transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1 / ∈ S and S = {s -1 | s ∈ S}. The Cayley graph Cay(G, S) on G with respect to S

Characterization of graphs which admit v

Characterization of graphs which admit vertex-transitive embeddings

✍ Jozef Širáň; Thomas W. Tucker 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

Large families of mutually embeddable ve

Large families of mutually embeddable vertex-transitive graphs

✍ Anthony Bonato; Claude Tardif 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract For each infinite cardinal κ, we give examples of 2^κ^ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all