The number of 4-cycles and the cyclomatic number of a finite simple graph

zbMATH Open1506.05099MaRDI QIDQ5060435FDOQ5060435

Authors Takayuki Hibi, Aki Mori, Hidefumi Ohsugi

Publication date 10 January 2023

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

zbMATH Keywords

first Betti numberTurán number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: Let $G$ be a finite connected simple graph with $n$ vertices and $m$ edges. We show that, when $G$ is not bipartite, the number of $4$-cycles contained in $G$ is at most $$. We further provide a short combinatorial proof of the bound $$ which holds for bipartite graphs.

Recommendations

• The number of 4-cycles in a graph
• The number of 4-cycles in triangle-free oriented graphs
• The decycling number of graphs \({G_{n{K_4}}}\)
• Enumeration of cyclically 4-connected cubic graphs
• THE NUMBER OF DISTINCT 4-CYCLES AND 2-MATCHINGS OF SOME ZERO-DIVISOR GRAPHS
• The number of \(n\)-cycles in a graph
• The cycle in 2-connected \([4,2]\)-graphs
• The minimum number of 4-cycles in a maximal planar graph with small number of vertices
• On the \(k\)-domination number, the domination number and the cycle of length four
• Common multiples of complete graphs and a 4-cycle

Cites work

• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• An upper bound on the sum of squares of degrees in a graph
• Binomial ideals
• Extremal edge polytopes
• Graphs with maximal number of adjacent pairs of edges
• Lectures on Polytopes
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximizing the sum of the squares of the degrees of a graph
• On the Number of 4-Edge Paths in Graphs With Given Edge Density
• On the number of certain subgraphs contained in graphs with a given number of edges
• On the number of cycles of lengthk in a maximal planar graph
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• Paths of length four
• Testing subgraphs in large graphs
• The number of edges of the edge polytope of a finite simple graph
• The number of generators of the powers of an ideal
• Toric ideals generalized by quadratic binomials

Cited in

(9)

• On the number of all substructures containing at most four edges
• A universality result for subcritical complex Gaussian multiplicative chaos
• THE NUMBER OF DISTINCT 4-CYCLES AND 2-MATCHINGS OF SOME ZERO-DIVISOR GRAPHS
• Critical Gaussian chaos: convergence and uniqueness in the derivative normalisation
• An elementary approach to Gaussian multiplicative chaos
• The number of 4-cycles in triangle-free oriented graphs
• scientific article; zbMATH DE number 5759522 (Why is no real title available?)
• The number of 4-cycles in a graph
• Uniqueness of critical Gaussian chaos

This page was built for publication: The number of $4$-cycles and the cyclomatic number of a finite simple graph

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