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

zbMATH Open1506.05099arXiv1801.06169MaRDI QIDQ5060435FDOQ5060435

Authors: Takayuki Hibi, Aki Mori, Hidefumi Ohsugi 

Publication date: 10 January 2023

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)