Upper bounds on the size of transitive subtournaments in digraphs

DOI10.1016/J.LAA.2017.04.030MaRDI QIDQ2013188zbMATH OpenOpenAlexFDO

Authors Koji Momihara, Sho Suda

Publication date 3 August 2017

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

block intersection polynomialdoubly regular tournamentHoffman's boundPaley tournamentregular digraphtransitive subtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: In this paper, we consider upper bounds on the size of transitive subtournaments in a digraph. In particular, we give an analogy of Hoffman's bound for the size of cocliques in a regular graph. Furthermore, we partially improve the Hoffman type bound for doubly regular tournaments by using the technique of Greaves and Soicher for strongly regular graphs [4], which gives a new application of block intersection polynomials.

Recommendations

• Some extremal properties concerning transitivity in graphs
• A note on a packing problem in transitive tournaments
• On tournaments free of large transitive subtournaments
• scientific article; zbMATH DE number 4195996
• On tournaments and their largest transitive subtournaments

Cites work

• A characterization of skew Hadamard matrices and doubly regular tournaments
• Block intersection polynomials
• Disproof of a conjecture of Erdös and moser on tournaments
• scientific article; zbMATH DE number 3985259 (Why is no real title available?)
• scientific article; zbMATH DE number 3668628 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• More on block intersection polynomials and new applications to graphs and block designs
• On cliques in edge-regular graphs
• ON EIGENVALUES AND COLORINGS OF GRAPHS, II
• On maximal transitive subtournaments
• On the clique number of a strongly regular graph
• On tournaments and their largest transitive subtournaments
• On tournaments free of large transitive subtournaments
• Squares and difference sets in finite fields

Cited in

(3)

• New bounds on the Ramsey number r ( I_m , L_n )
• On the restricted isometry property of the Paley matrix
• Sizes and transmissions of digraphs with a given clique number

This page was built for publication: Upper bounds on the size of transitive subtournaments in digraphs

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