SOME CONDITIONS IMPLYING STABILITY OF GRAPHS ADEMIR HUJDUROVI C AND DOR DE MITROVI C Abstract. A graph Xis said to be unstable if the direct product XK2

2025-05-03 0 0 354.22KB 13 页 10玖币
侵权投诉
SOME CONDITIONS IMPLYING STABILITY OF GRAPHS
ADEMIR HUJDUROVI´
C AND ¯
DOR¯
DE MITROVI´
C
Abstract. A graph Xis said to be unstable if the direct product X×K2
(also called the canonical double cover of X) has automorphisms that
do not come from automorphisms of its factors Xand K2. It is non-
trivially unstable if it is unstable, connected, non-bipartite, 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 non-trivially
unstable triangle-free graphs of diameter 2. An interesting construction
of non-trivially unstable graphs is given and several open problems are
posed.
1. Introduction
All graphs considered in this paper are finite, simple and undirected. For
a graph X, we denote by V(X), E(X) and Aut(X) the vertex set, the edge
set and the automorphism group of X, respectively. The canonical bipartite
double cover (also called the bipartite double cover or the Kronecker cover)
of a graph X, denoted by BX, is the direct product X×K2(where K2
denotes the complete graph on two vertices). This means that V(BX) =
V(X)× {0,1}and E(BX) = {{(x, 0),(y, 1)} | {x, y} ∈ E(X)}.
Canonical double covers have proven to play an important role in algebraic
graph theory and have been studied by multiple groups of authors from a
variety of perspectives [3, 9, 12, 15, 18, 19, 20, 24, 26]. It is well-known
that BX is connected if and only if Xis connected and non-bipartite, see
[7]. It is easy to see that Aut(BX) contains a subgroup isomorphic to
Aut(X)×S2. However, determining the full automorphism group of BX is
not as trivial. Hammack and Imrich [8] investigated vertex-transitivity of
the direct product of graphs, and proved that for a non-bipartite graph X
and a bipartite graph Y, their direct product X×Yis vertex-transitive if
and only if both BX and Yare vertex-transitive. Hence, the problem of
vertex-transitivity of the direct product of graphs reduces to the problem of
vertex-transitivity of canonical double covers.
If Aut(BX) is isomorphic to Aut(X)×S2then the graph Xis called
stable, otherwise it is called unstable. This concept was first defined by
Date: October 28, 2022.
1
arXiv:2210.15249v1 [math.CO] 27 Oct 2022
2 ADEMIR HUJDUROVI ´
C AND ¯
DOR¯
DE MITROVI ´
C
Maruˇsiˇc et al. [14]. A graph is said to be twin-free (also called worthy,vertex-
determining or irreducible) if distinct vertices have different neighbourhoods.
It is not difficult to prove that disconnected graphs, bipartite graphs with
non-trivial automorphism groups, and graphs containing twin vertices are
unstable. These graphs are considered trivially unstable. An unstable graph
is said to be non-trivially unstable if it is non-bipartite, connected, and twin-
free.
In [25], Wilson gave several sufficient conditions for a graph to be unsta-
ble, which he then applied to families of circulants, Rose Window graphs,
toroidal graphs and generalized Petersen graphs. The characterization of
unstable generalized Petersen graphs was obtained by Qin, Xia and Zhou in
[22]. Stability of circulant graphs was studied by Qin, Xia and Zhou in [21],
where it was proven that there are no non-trivially unstable arc-transitive
circulants. In [4], it was proven by Fernandez and Hujdurovi´c that there are
no non-trivially unstable circulants of odd order. In [17], Morris extended
this result by proving that there are no non-trivially unstable Cayley graphs
on Abelian groups of odd order. In [10], the complete classification of un-
stable circulants of valency at most 7 was obtained, while in [11] several
constructions of unstable circulants were presented, and unstable circlants
of order 2p(with pa prime) were classified.
Although it is in some sense expected that most graphs are stable, there
are not many results giving sufficient conditions for a general graph to be
stable. The main motivation for this paper comes from the work of Surowski
[23] on stability of arc-transitive graphs, where he describes two sufficient
stability conditions, namely [23, Proposition 2.1] for vertex-transitive graphs
of diameter at least 4 and [23, Proposition 2.2] for strongly regular graphs.
The first of these results has been shown not to hold by Lauri, Mizzi and
Scapellato in [13], where the authors constructed an infinite family of coun-
terexamples. In the same article, the authors pointed out that the proof of
the second result seems incomplete, hence asking for a further investigation
of stability of strongly regular graphs.
In Section 3, we will discuss the original statement of Surowski’s first sta-
bility criterion and an infinite family of counterexamples by Lauri, Mizzi and
Scapellato (see Proposition 3.1). Then we will explain the mistake in the
original proof and fix it by introducing additional assumptions, consequently
obtaining a valid stability criterion in Proposition 3.2, which no longer re-
quires the graph to be vertex-transitive. Then we turn our attention to the
second result of Surowski concerning strongly regular graphs, which turned
out to be correct, although its original proof was slightly incomplete. We
prove a generalized version of this result in Proposition 3.5 that applies to
a wider class of graphs.
In Section 4, to contrast the previous results which required every edge
of a graph to lie on a triangle, we consider triangle-free graphs, and prove
that there are no non-trivially unstable triangle-free graphs of diameter 2
(see Theorem 4.1).
SOME CONDITIONS IMPLYING STABILITY OF GRAPHS 3
In Section 5, we present an interesting construction of non-trivially un-
stable graphs, which shows that every connected, non-bipartite, twin-free
graph of order nis an induced subgraph of a non-trivially unstable graph
of order n+ 4. With the help of a computer, we check that most of the
non-trivially unstable graphs up to 10 vertices can be obtained using this
construction.
2. Preliminaries
Let Xbe a graph and BX its bipartite double cover. For an automor-
phism ϕof X, it is easy to see that the function ϕ, defined by ϕ(x, i) =
(ϕ(x), i) is an automorphism of BX, called the lift of ϕ. It is straightfor-
ward to check that the function τdefined by τ(x, i)=(x, i + 1) (the second
coordinate is calculated modulo 2) is also an automorphism of BX.
The subgroup generated by τand the lifts ϕwith ϕ∈Aut(X) is isomor-
phic to Aut(X)×S2. Automorphisms of BX that belong to this subgroup
are called the expected automorphisms of BX (see [25]). If an automorphism
of BX does not belong to this subgroup, it is called unexpected. Using this
terminology, a graph Xis stable if and only if every automorphism of BX
is expected.
The following result is known and will be used later on for establishing
stability of graphs. For the sake of completeness, we provide a short proof.
Lemma 2.1. Let Xbe a connected, non-bipartite graph, and let αbe an
automorphism of BX. Then αis an expected automorphism of BX if and
only if for every x∈V(X), it holds that α({(x, 0),(x, 1)}) = {(y, 0),(y, 1)}
for some y∈V(X).
Proof. Since Xis a connected and non-bipartite graph, it follows that BX is
connected and bipartite with bipartite sets V(X)× {0}and V(X)× {1}. If
αinterchanges the bipartite sets, then one can consider ατ instead. Hence,
without loss of generality, we can assume that αpreserves the sets V(X)×
{0}and V(X)× {1}. Then αsatisfies the condition from Lemma 2.1 if and
only if α(x, i)=(ϕ(x), i), for some permutation ϕof V(BX). It is easy to
see that the map (x, i)7→ (ϕ(x), i) is an automorphism of BX if and only if
ϕis an automorphism of X.
It is not difficult to show that even cycles are unstable, while odd cycles
are stable. Moreover, we have the following easy example.
Example 2.2 (Qin-Xia-Zhou,[21, Example 2.2]).The complete graph Kn
is unstable if and only if n= 2.
Recall that a strongly regular graph with parameters (n, k, λ, µ) is a k-
regular connected graph of diameter 2 on nvertices such that every edge lies
on λtriangles, and any two non-adjacent vertices have exactly µneighbours
in common. Note that µ > 0 and that a strongly regular graph is twin-free
if and only if k > µ.
摘要：

SOMECONDITIONSIMPLYINGSTABILITYOFGRAPHSADEMIRHUJDUROVICANDDORDEMITROVICAbstract.AgraphXissaidtobeunstableifthedirectproductXK2(alsocalledthecanonicaldoublecoverofX)hasautomorphismsthatdonotcomefromautomorphismsofitsfactorsXandK2.Itisnon-triviallyunstableifitisunstable,connected,non-bipartite,an...

展开>> 收起<<
SOME CONDITIONS IMPLYING STABILITY OF GRAPHS ADEMIR HUJDUROVI C AND DOR DE MITROVI C Abstract. A graph Xis said to be unstable if the direct product XK2.pdf

共13页,预览3页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：13 页 大小：354.22KB 格式：PDF 时间：2025-05-03

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 13
评分 收藏
分享
立即下载
客服
关注