Effect of graph operations on graph associahedra
| Autor: | Gargantini, Ana, Pastine, Adrián, Torres, Pablo |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Given a graph $G$, we determine the structure of the rotation graph of a graph obtained by applying certain operations to $G$. Specifically, we consider the operations of adding a simplicial vertex, adding a true twin to a vertex, and the two closely related operations of deleting the set of edges from a subgraph induced by a set of true twins, and adding a false twin to a vertex. We describe how applying these operations to a graph affects the structure of its rotation graph. Furthermore, by using this description, we study chromatic number, distance, and diameter in rotation graphs. In particular, we establish conditions under which the chromatic number of the rotation graphs is preserved. As an interesting consequence, we obtain that the chromatic number of the rotation graphs of threshold graphs (which includes complete split graphs and star graphs) and of complete bipartite graphs is 3. We also provide a new lower bound for $\text{diam}(\mathcal{R}(G-S))$ in terms of $\text{diam}(\mathcal{R}(G))$, where $S$ is the set of edges of the subgraph of $G$ induced by a set of true twins. As a consequence, we improve the known lower bound for the diameter of the rotation graph of balanced complete bipartite graphs, allowing us to compute the exact value of $\text{diam}(\mathcal{R}(K_{2,q}))$ for $q\in\{3,4,5,6,7,8\}$. Comment: This version is a replacement of a previous arXiv preprint by the name of "On the structure and diameter of graph associahedra of graphs with a set of true twins", which dealt only with Sections 2.3 and 4 of this article |
| Databáze: | arXiv |
| Externí odkaz: |
|