A characterization of some graphs which do not contain 3-claws (Q1313824): Difference between revisions

Finite graphs with \(V=\{0,1,2,\dots,3m\}\) and where vertices \(i\) and \(j\) with \(j>1\) are adjacent whenever \(j-i \not \equiv 2 \pmod 3\) are called \(N_ m\)-graphs. Thus, in particular \(N_ 1\) is a quadrangle and \(N_ 2\) is isomorphic to the complement of a 7-cycle. And, up to isomorphism, the so-called (finite) \(N\)-graphs are precisely these graphs \(N_ m\). An \(n\)-claw of a graph is a subgraph on \(n+1\) vertices, one of which is adjacent to all the others, while no two other vertices are adjacent, and finally the set of vertices of a graph at distance at most one to the vertex \(\alpha\) let be denoted by \(\alpha^ \perp\). The authors prove the result that a connected and not complete graph \(\Gamma\) is isomorphic to a lattice graph or to an \(N\)-graph when it satisfies the following three conditions: (1) \(\Gamma\) has no 3-claws. (2) For any two vertices \(\alpha\) and \(\beta\) at distance two, the induced subgraph \(\alpha^ \perp \cap \beta^ \perp\) is disconnected. (3) For any two distinct vertices \(\alpha\) and \(\beta\), we have \(\alpha^ \perp \neq \beta^ \perp\).