Mathematics – Combinatorics
Scientific paper
2003-06-10
Mathematics
Combinatorics
16 pages, 4 figures, submitted to proceedings of "Cycles and Colorings" workshop [2002, Stara Lesna, Slovakia]
Scientific paper
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.
Farrugia Alastair
No associations
LandOfFree
Dually vertex oblique graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dually vertex oblique graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dually vertex oblique graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-367960