Note on a Turán-type problem on distances.

zbMATH Open1349.05092arXiv1312.1013MaRDI QIDQ2804796FDOQ2804796

Authors: Yongtang Shi, Jun Yue, Xueliang Li, Jing Ma 

Publication date: 4 May 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

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 $vinV(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. {�f 29}(6), 1927--1942 (2012)].

Full work available at URL: https://arxiv.org/abs/1312.1013

Recommendations

• A note on Turán's theorem
• A Turán-type problem on distances in graphs
• scientific article; zbMATH DE number 29733
• A note on a theorem of Turan
• scientific article
• scientific article; zbMATH DE number 817518
• Some remarks on Turán's inequality
• scientific article
• Turán type results for distance graphs
• Note on a problem of Q. I. Rahman and P. Turán

zbMATH Keywords

distanceforbidden subgraphTurán-type problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Cited In (3)

• On the Wiener polarity index of graphs
• The Nordhaus-Gaddum-type inequality for the Wiener polarity index
• Ordering chemical trees by Wiener polarity index

This page was built for publication: Note on a Turán-type problem on distances.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804796)