Extremal graph for intersecting odd cycles

MaRDI QIDQ286112zbMATH OpenFDO

Authors Yu Qiu, Boyuan Liu, Xinmin Hou

Publication date 20 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08373, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal graphintersecting odd cyclesTurán graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Tur'{a}n graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Tur'{a}n Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erd"{o}s et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

Review text

Summary: An extremal graph for a graph \(H\) on \(n\) vertices is a graph on \(n\) vertices with maximum number of edges that does not contain \(H\) as a subgraph. Let \(T_{n,r}\) be the Turán graph, which is the complete \(r\)-partite graph on \(n\) vertices with part sizes that differ by at most one. The well-known Turán Theorem states that \(T_{n,r}\) is the only extremal graph for complete graph \(K_{r+1}\). \textit{P. Erdős} et al. [J. Comb. Theory, Ser. B 64, No. 1, 89--100 (1995; Zbl 0822.05036)] determined the extremal graphs for intersecting triangles and \textit{G. Chen} et al. [ibid. 89, No. 2, 159--171 (2003; Zbl 1031.05069)] determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

Recommendations

• Extremal graphs for intersecting cliques
• Turán number and decomposition number of intersecting odd cycles
• The spectral radius of graphs with no intersecting odd cycles
• scientific article; zbMATH DE number 3970790
• Extremal numbers for odd cycles

Cites work

• Degrees and matchings
• Extremal graphs for blow-ups of cycles and trees
• Extremal graphs for intersecting cliques
• Extremal graphs for intersecting triangles
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)

Cited in

(20)

• Extremal graphs for intersecting cliques
• Extremal graphs for intersecting triangles
• The spectral radius of graphs with no intersecting odd cycles
• Extremal graphs of the \(p\)th power of paths
• Extremal graphs for odd-ballooning of paths and cycles
• The Turán number for the edge blow-up of trees
• Turán number and decomposition number of intersecting odd cycles
• Extremal graphs for blow-ups of keyrings
• Extremal graphs for edge blow-up of graphs
• Odd cycle transversal in mixed graphs
• Extremal graphs for the k-flower
• Extremal graphs for odd wheels
• Turán number of the family consisting of a blow-up of a cycle and a blow-up of a star
• Turán number for odd‐ballooning of trees
• Spectral Turán problems for intersecting even cycles
• Turán number of the odd-ballooning of complete bipartite graphs
• Extremal graphs for the odd prism
• Extremal graphs for disjoint union of vertex-critical graphs
• Decomposition family and spectral extremal problems on non-bipartite graphs
• Spectral skeletons and applications

This page was built for publication: Extremal graph for intersecting odd cycles

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