Dually vertex oblique graphs
Abstract
Description
A vertex with neighbours of degrees $d_1 \geq ... \geq d_r$ has {\em vertex type} $(d_1, ..., d_r)$. A graph is {\em vertex-oblique} if each vertex has a distinct vertex-type. While no graph can have distinct degrees, Schreyer, Walther and Mel'nikov [Vertex oblique graphs, same proceedings] have constructed infinite classes of {\em super vertex-oblique} graphs, where the degree-types of $G$ are distinct even from the degree types of $\bar{G}$.
$G$ is vertex oblique iff $\bar{G}$ is; but $G$ and $\bar{G}$ cannot be isomorphic, since self-complementary graphs always have non-trivial automorphisms. However, we show by construction that there are {\em dually vertex-oblique graphs} of order $n$, where the vertex-type sequence of $G$ is the same as that of $\bar{G}$; they exist iff $n \equiv 0$ or $1 \pmod 4, n \geq 8$, and for $n \geq 12$ we can require them to be split graphs.
We also show that a dually vertex-oblique graph and its complement are never the unique pair of graphs that have a particular vertex-type sequence; but there are infinitely many super vertex-oblique graphs whose vertex-type sequence is unique.
16 pages, 4 figures, submitted to proceedings of "Cycles and Colorings" workshop [2002, Stara Lesna, Slovakia]
16 pages, 4 figures, submitted to proceedings of "Cycles and Colorings" workshop [2002, Stara Lesna, Slovakia]