Dually vertex oblique graphs
| dc.creator | Farrugia, Alastair | |
| dc.date | 2003-06-10 | |
| dc.date.accessioned | 2026-07-07T04:58:42Z | |
| dc.date.available | 2026-07-07T04:58:42Z | |
| dc.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. | |
| dc.description | 16 pages, 4 figures, submitted to proceedings of "Cycles and Colorings" workshop [2002, Stara Lesna, Slovakia] | |
| dc.identifier | https://arxiv.org/abs/math/0306154 | |
| dc.identifier | http://arxiv.org/abs/math/0306154 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67746 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C99 (Primary) 05C07 (Secondary) | |
| dc.title | Dually vertex oblique graphs | |
| dc.type | text |