pith. sign in

arxiv: 1312.1013 · v1 · pith:MRKSVUUAnew · submitted 2013-12-04 · 🧮 math.CO

A Tur\'an-type problem on distance two

classification 🧮 math.CO
keywords distancean-typegraphstyomkynuzzellverticesproblemanswers
0
0 comments X
read the original abstract

A new tur\'an-type problem on distances on graphs was introduced by Tyomkyn and Uzzell. In this paper, we focus on the case that the distance is two. We primely show that for any value of $n$, a graph on $n$ vertices without three vertices pairwise at distance $2$, if it has a vertex $v \in V(G)$, whose neighbours are covered by at most two cliques, then it has at most $(n^2 - 1)/4 + 1$ pairs of vertices at distance $2$. This partially answers a guess of Tyomkyn and Uzzell [Tyomkyn, M., Uzzell, A.J.: A new Tur\'an-Type promble on distaces of graphs. Graphs Combin. {\bf 29}(6), 1927--1942 (2012)].

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.