Some conditions implying stability of graphs
Open Access
- 7 August 2023
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 105 (1) , 98-109
Abstract
A graph is said to be unstable if the direct product (also called the canonical double cover of ) has automorphisms that do not come from automorphisms of its factors and . It is nontrivially unstable if it is unstable, connected, nonbipartite, and distinct vertices have distinct sets of neighbours. In this paper, we prove two sufficient conditions for stability of graphs in which every edge lies on a triangle, revising an incorrect claim of Surowski and filling in some gaps in the proof of another one. We also consider triangle‐free graphs, and prove that there are no nontrivially unstable triangle‐free graphs of diameter 2. An interesting construction of nontrivially unstable graphs is given and several open problems are posed.Keywords
All Related Versions
Funding Information
- The Slovenian Research and Innovation Agency
This publication has 23 references indexed in Scilit:
- Bipartite Kneser Graphs are HamiltonianCombinatorica, 2016
- Unexpected symmetries in unstable graphsJournal of Combinatorial Theory, Series B, 2008
- On 2-fold covers of graphsJournal of Combinatorial Theory, Series B, 2008
- Stability of arc‐transitive graphsJournal of Graph Theory, 2001
- Algebraic Graph Theory2001
- The Magma Algebra System I: The User LanguageJournal of Symbolic Computation, 1997
- Digraphs having the same canonical double coveringDiscrete Mathematics, 1997
- Regular Embeddings of Canonical Double Coverings of GraphsJournal of Combinatorial Theory, Series B, 1996
- A characterization of particular symmetric (0,1) matricesLinear Algebra and its Applications, 1989
- Double covers of graphsBulletin of the Australian Mathematical Society, 1976