Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths

DOI10.1137/140981496MaRDI QIDQ3195131zbMATH OpenOpenAlexFDO

Authors A. Galluccio, Nicola Apollonio

Publication date 21 October 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

balanced/perfect graphbalanced/perfect matrices

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Hypergraphs (05C65) Perfect graphs (05C17)

Abstract: A $0,1$-matrix $mathsfA$ is balanced if it does not contain a submatrix of odd order having exactly two 1's per row and per column. A graph is balanced if its clique-matrix is balanced. No characterization of minimally unbalanced graphs is known, and even no conjecture on the structure of such graphs has been posed, contrarily to what happened for perfect graphs. In this paper, we provide such a characterization for the class of diamond-free graphs and establish a connection between minimally unbalanced diamond-free graphs and Dyck-paths.

Recommendations

• Minimum distance-unbalancedness of graphs with diameter 2 and given number of edges
• On minimum balanced bipartitions of triangle-free graphs
• On acyclic and unicyclic graphs whose minimum rank equals the diameter
• Minimal digraphs with given imbalance sequence
• On the connectivity of diamond-free graphs
• Unimodality and Dyck paths
• scientific article; zbMATH DE number 1439406
• scientific article; zbMATH DE number 1303530
• scientific article; zbMATH DE number 21730
• An invariant for minimum triangle-free graphs

Cites work

• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• A new bijection between ordered trees and legal bracketings
• Algorithmic aspects of clique-transversal and clique-independent sets
• Balanced matrices
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• Clique-perfectness and balancedness of some graph classes
• Covering all cliques of a graph
• Decomposition of balanced matrices
• Distance-hereditary graphs are clique-perfect
• Dyck path enumeration
• Neighborhood perfect graphs
• On balanced graphs
• On clique-perfect and K-perfect graphs
• On minimal forbidden subgraph characterizations of balanced graphs
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Properties of balanced and perfect matrices
• Structural properties and decomposition of linear balanced matrices
• Testing balancedness and perfection of linear matrices
• The strong perfect graph theorem

Cited in

(1)

• On some graph classes related to perfect graphs: a survey

This page was built for publication: Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths

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