Balancedness of subclasses of circular-arc graphs
Copyright policy )Balancedness of subclasses of circular-arc graphs
Graph Theory A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs.
- National Scientific and Technical Research Council Argentina
- University of Chile Chile
- Institut Pascal France
- National University of General Sarmiento Argentina
- Clermont Université France
Cograph, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Geometry, Pathwidth, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Optical Code Division Multiple Access, Chordal graph, Engineering, Clique-sum, QA1-939, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, https://purl.org/becyt/ford/1.1, Electrical and Electronic Engineering, https://purl.org/becyt/ford/1, clique-perfect graphs, perfect graphs, Graph Spectra and Topological Indices, Line graph, Indifference graph, Discrete mathematics, circular-arc graphs, Block graph, Vertex (graph theory), [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Arc (geometry), Computational Theory and Mathematics, Combinatorics, Graph Theory, Computer Science, Physical Sciences, Split graph, balanced graphs, Geometry and Topology, coordinated graphs, 1-planar graph, Mathematics, Graph Theory and Algorithms
Cograph, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Geometry, Pathwidth, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Optical Code Division Multiple Access, Chordal graph, Engineering, Clique-sum, QA1-939, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, https://purl.org/becyt/ford/1.1, Electrical and Electronic Engineering, https://purl.org/becyt/ford/1, clique-perfect graphs, perfect graphs, Graph Spectra and Topological Indices, Line graph, Indifference graph, Discrete mathematics, circular-arc graphs, Block graph, Vertex (graph theory), [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Arc (geometry), Computational Theory and Mathematics, Combinatorics, Graph Theory, Computer Science, Physical Sciences, Split graph, balanced graphs, Geometry and Topology, coordinated graphs, 1-planar graph, Mathematics, Graph Theory and Algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!