Search

The canonical double cover D(Γ) of a graph Γ is the direct product of Γ and K2. If Aut(D(Γ))≅Aut(Γ)×Z2 then Γ is called stable; otherwise Γ is called unstable. An unstable graph is said to be nontrivially unstable if it is connected, non‐bipartite and no two vertices have the same neighborhood. In 2008 Wilson conjectured that, if the generalized Petersen graph GP(n,k) is nontrivially unstable, then both n and k are even, and either n/2 is odd and k2≡±1(mod n/2), or n=4k. In this note we prove that this conjecture is true. At the same time we determine all possible isomorphisms among the generalized Petersen graphs, the canonical double covers of the generalized Petersen graphs, and the double generalized Petersen graphs. Based on these we completely determine the full automorphism group of the canonical double cover of GP(n,k) for any pair of integers n,k with 1⩽k

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers [ABSTRACT FROM AUTHOR]

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G-symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G-symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given. [ABSTRACT FROM AUTHOR]

Unitary graphs are arc-transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc-transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power [ABSTRACT FROM AUTHOR]