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

MaRDI QIDQ2804796zbMATH OpenFDO

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

Publication date 4 May 2016

Published in Ars Combinatoria (Search for Journal in Brave)

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

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)

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)].

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; zbMATH DE number 3844296
• scientific article; zbMATH DE number 817518
• Some remarks on Turán's inequality
• scientific article; zbMATH DE number 4200236
• Turán type results for distance graphs
• Note on a problem of Q. I. Rahman and P. Turán

Cited in

(4)

• Ordering chemical trees by Wiener polarity index
• Turán-type bounds for distance graphs
• On the Wiener polarity index of graphs
• The Nordhaus-Gaddum-type inequality for the 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)