Source-linked AI summary
There are no nontrivial chordal square-complementary graphs
Pierre Aboulker, Martin Milanič, Peter Muršič, Miguel A. Pizaña
TL;DR
The paper addresses whether nontrivial square-complementary graphs can be chordal or contain simplicial vertices. It proves these possibilities, as well as distance-hereditary examples, do not occur.
Problem
The paper addresses open questions about whether nontrivial square-complementary graphs can be chordal or contain simplicial vertices.
Source: §1 · p. 1Method
The authors analyze dominating pairs and use twin-orbit deletion in minimal square-complementary graphs.
Source: §3 · pp. 3–4Results
Nontrivial square-complementary graphs have no dominated or simplicial vertices, are not chordal, and are not distance-hereditary.
Source: §3 · p. 3Takeaways & Limitations
Abstract
from arXiv · showhide
We study square-complementary graphs $G$ (satisfying $G^2 \cong \overline{G}$). We show that in such graphs, no two vertices have comparable closed neighborhoods. This implies that nontrivial square-complementary graphs have no simplicial vertices and are not chordal, thus solving two open problems posed in Discrete Mathematics 327 (2014) 62-75. We also show that no nontrivial square-complementary graph is distance-hereditary.
1 Introduction
The paper answers open questions about chordal and simplicial-vertex structure in nontrivial square-complementary graphs, and also excludes distance-hereditary examples. These results extend earlier exclusions for other graph classes.
1 Introduction
- Nontrivial square-complementary graphs have no simplicial vertices and are not chordal, answering Problems 5 and 6 posed in.The paper also excludes nontrivial distance-hereditary square-complementary graphs.Source: §1 · pp. 1–2
- The chordal exclusion also rules out nontrivial square-complementary split, interval, and block graphs.The distance-hereditary result extends the known exclusion of nontrivial square-complementary cographs.Source: §1 · pp. 1–2
- A prior mention of the chordal result referred to a preprint, but the authors knew of no published proof.The mention appeared in [12, p. 185], referring to a preprint by Capobianco and Kim.Source: §1 · p. 2
2 Preliminaries
The preliminaries define square-complementary graphs and establish graph, neighborhood, distance, and permutation terminology used in the results.
2 Preliminaries
- A vertex is dominated when its closed neighborhood is contained in another's; twins have equal closed or open neighborhoods.Simplicial vertices have closed neighborhoods inducing cliques, while pendant vertices have degree one.Source: §2 · p. 2
- A graph is square-complementary when its square is isomorphic to its complement; the square adds edges between vertices at distance two.In a square-complementary graph, adjacency in the square corresponds to distance at least three in the original graph.Source: §2 · p. 2
- Every nontrivial square-complementary graph is connected, has radius 3, and has diameter 3 or 4.The paper also notes that square-complementary graphs have no pendant vertices.Source: §2 · p. 2
- The preliminaries define chordal graphs by the chord condition on cycles of length at least four and distance-hereditary graphs by preservation of distances in connected induced subgraphs.Chordal graphs contain simplicial vertices; nontrivial distance-hereditary graphs contain a pendant vertex or twins.Source: §2 · p. 2
- A permutation's orbit collects the iterates of a vertex or set, and a set is invariant when the permutation maps it to itself.The exponent is the least positive power of the permutation equal to the identity.Source: §2 · p. 3
3 Results
The results exclude dominated vertices, simplicial vertices, chordal graphs, and distance-hereditary graphs among nontrivial square-complementary graphs. A twin-orbit deletion argument supports the minimal-graph conclusion.
3 Results
- A nontrivial square-complementary graph has no dominated vertices, true twins, or simplicial vertices.Any dominating pair in the graph becomes a false dominating pair in its square, and the graph itself cannot contain true dominating pairs.Source: §3 · p. 3
- A nontrivial square-complementary graph is not chordal.This follows from the preceding exclusion of simplicial vertices together with the fact that chordal graphs contain simplicial vertices.Source: §3 · p. 3
- A minimal nontrivial square-complementary graph contains no true or false twins, and no nontrivial square-complementary graph is distance-hereditary.The proof assumes a minimal example and removes an orbit of twins; the resulting induced subgraph remains distance-hereditary and square-complementary, leading to a contradiction.Source: §3 · pp. 3–4
- In the twin-orbit argument, deleting the orbit leaves a smaller square-complementary graph, which minimality forces to be trivial.The argument uses an isomorphism from the square to the graph, adjusts it so the twin's orbit returns to its starting vertex, then restricts the isomorphism after deletion; the remaining possibility would be a two-vertex square-complementary graph, which does not exist.Source: §3 · p. 4
4 Alternate proof of Theorem 3.3
An alternate proof rules out chordal square-complementary graphs by building a five-part partition and showing that its structure forces the square graph to have radius at most two, incompatible with isomorphism to the original graph.
4 Alternate proof of Theorem 3.3
- The proof starts from a diameter-4 chordal squco graph, using the chordal bound d(G) ≥ 2r(G)−2 [7] and r(G)=3.The bound forces d(G)=4; the proof then partitions vertices into distance layers from a pair at distance 4.Source: §4 · p. 5
- The components C and D of G−S have the same neighborhood S, making S a minimal separator and therefore a clique in chordal G [9].The proof places C in the distance layers L3∪L4 and shows S⊆L2 before establishing the common-neighborhood condition.Source: §4 · p. 5
- The distance-from-S construction yields five pairwise disjoint, nonempty parts A2, A1, S, B1, and B2, with no A_i or B_i for i≥3.Source: §4 · p. 6
- In G², A2 is complete to B1∪B2 and A1 is complete to B2, while A1 and B1 are anticomplete to S.These relations follow from the parts' distances in G and S being a clique in G.Source: §4 · p. 6
- If neither A2 nor B2 is a clique in G², nonadjacent pairs from each induce a C4, contradicting chordality of G².G² is isomorphic to chordal G, so it must also be chordal.Source: §4 · p. 6
- A clique in either A2 or B2 in G² yields a vertex of eccentricity at most 2, contradicting the radius-3 chordal squco graph.Since G² is isomorphic to G, their radii must agree.Source: §4 · pp. 5–6