In a reconfiguration setting, each clique of a graph G is viewed as a set of tokens placed on vertices of G such that no vertex has more than one token and any two tokens are adjacent. Three well-known reconfiguration rules have been studied in the literature: Token Jumping ( \(\textsf{TJ}\) ), Token Sliding ( \(\textsf{TS}\) ), and Token Addition/Removal ( \(\textsf{TAR}\) ). Given a graph G and a reconfiguration rule \(\textsf{R} \in \{\textsf{TS}, \textsf{TJ}, \textsf{TAR}\}\) , a reconfiguration graph of k-cliques of G, denoted by \(\textsf{R}_k(G)\) , is the graph whose vertices are cliques of G of size k and two vertices are adjacent if one can be obtained from the other by applying \(\textsf{R}\) exactly once. In this paper, we initiate the study of structural properties of reconfiguration graphs of cliques, proving several interesting results primarily under \(\textsf{TS}\) and \(\textsf{TJ}\) rules. In particular, we establish a formula relating the clique number of G and that of \(\textsf{TS}_k(G)\) , and bound the chromatic number of \(\textsf{TS}_k(G)\) via that of an appropriate Johnson graph. Additionally, we present an algorithm to construct \(\textsf{TS}_{\omega (G)-1}(G)\) from \(\textsf{TJ}_{\omega (G)}(G)\) and derive structural properties of \(\textsf{TJ}_{\omega (G)}(G)\) graphs, where \(\omega (G)\) denotes the clique number of G. Finally, we show that \(\textsf{TS}_k(G)\) is planar whenever G is planar and establish bounds on the number of 3- and 4-cliques based on results concerning \(\textsf{TS}_k(G)\) graphs. In particular, we prove that any planar graph G with n vertices can contain at most \(3n - 8\) triangles, which aligns with the classical bound on maximal planar graphs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Note on Reconfiguration Graphs of Cliques

  • Nhat-Quan Lam,
  • Huu-An Phan,
  • Duc A. Hoang

摘要

In a reconfiguration setting, each clique of a graph G is viewed as a set of tokens placed on vertices of G such that no vertex has more than one token and any two tokens are adjacent. Three well-known reconfiguration rules have been studied in the literature: Token Jumping ( \(\textsf{TJ}\) ), Token Sliding ( \(\textsf{TS}\) ), and Token Addition/Removal ( \(\textsf{TAR}\) ). Given a graph G and a reconfiguration rule \(\textsf{R} \in \{\textsf{TS}, \textsf{TJ}, \textsf{TAR}\}\) , a reconfiguration graph of k-cliques of G, denoted by \(\textsf{R}_k(G)\) , is the graph whose vertices are cliques of G of size k and two vertices are adjacent if one can be obtained from the other by applying \(\textsf{R}\) exactly once. In this paper, we initiate the study of structural properties of reconfiguration graphs of cliques, proving several interesting results primarily under \(\textsf{TS}\) and \(\textsf{TJ}\) rules. In particular, we establish a formula relating the clique number of G and that of \(\textsf{TS}_k(G)\) , and bound the chromatic number of \(\textsf{TS}_k(G)\) via that of an appropriate Johnson graph. Additionally, we present an algorithm to construct \(\textsf{TS}_{\omega (G)-1}(G)\) from \(\textsf{TJ}_{\omega (G)}(G)\) and derive structural properties of \(\textsf{TJ}_{\omega (G)}(G)\) graphs, where \(\omega (G)\) denotes the clique number of G. Finally, we show that \(\textsf{TS}_k(G)\) is planar whenever G is planar and establish bounds on the number of 3- and 4-cliques based on results concerning \(\textsf{TS}_k(G)\) graphs. In particular, we prove that any planar graph G with n vertices can contain at most \(3n - 8\) triangles, which aligns with the classical bound on maximal planar graphs.