Some extremal properties concerning transitivity in graphs

DOI10.1007/BF02018593MaRDI QIDQ2561235zbMATH OpenOpenAlexWikidataFDO

Authors C. C. Harner, R. C. Entringer, P. Erdős

Publication date 1973

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02018593

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Review text

A directed graph \(D\) is transitive iff arc \(ac\) is in \(D\) whenever arcs \(ab\) and \(bc\) are in \(D\). We show that for all tournaments \(T_n\) on \(n\) points, with \(0 \left(2^{\binom{n}{2}} \right)\) exceptions, the largest transitive subgraph of \(T_n\) contains fewer than \({1 \over 4}\binom{n}{2}+cn^{3/2}\) arcs for a suitable constant \(c\). Results concerning the size of bipartite subgraphs of tournaments and transitive graphs are also obtained.

Recommendations

• Subdivisions of transitive tournaments
• A note on a packing problem in transitive tournaments
• On tournaments free of large transitive subtournaments
• On a generalization of transitivity for digraphs
• On tournaments and their largest transitive subtournaments

Cites work

• On Sets of Consistent Arcs in a Tournament
• Optimal ranking of tournaments

Cited in

(18)

• Extremal digraph results for topological complete subgraphs
• On adjacency-transitive graphs
• On tournaments free of large transitive subtournaments
• Subdivisions of transitive tournaments
• Random regular tournaments
• \(\text{TT}_n\)-maximal digraphs of the minimum size
• Upper bounds on the size of transitive subtournaments in digraphs
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• B-stable subgraphs in undirected graphs
• scientific article; zbMATH DE number 2077809 (Why is no real title available?)
• scientific article; zbMATH DE number 2150377 (Why is no real title available?)
• Transitivity of trees
• scientific article; zbMATH DE number 5499517 (Why is no real title available?)
• Algorithms for finding maximum transitive subtournaments
• The maximal transitive subtournaments of a digraph: the operator
• Decomposing oriented graphs into transitive tournaments
• A note on decompositions of transitive tournaments
• Induced subgraphs of Ramsey graphs with many distinct degrees

This page was built for publication: Some extremal properties concerning transitivity in graphs

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