The edge inducibility of graphs

DOI10.1007/BF01886309zbMath0461.05037OpenAlexW2025468003MaRDI QIDQ3910550

Yehoshua Perl, Martin Charles Golumbic

Publication date: 1980

Published in: Acta Mathematica Academiae Scientiarum Hungaricae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01886309

zbMATH Keywords

edge inducibility

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Related Items

Extreme chordal doubly nonnegative matrices with given row sums, Linear time optimization algorithms for \(P_ 4\)-sparse graphs, Weighted parameters in \((P_5,\overline {P_5})\)-free graphs, The inducibility of complete bipartite graphs, Object-oriented interaction in resource constrained scheduling, New sequential and parallel algorithms for interval graph recognition, An efficient parallel algorithm for scheduling interval ordered tasks, Solving the single step graph searching problem by solving the maximum two-independent set problem, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Counting clique trees and computing perfect elimination schemes in parallel, A new approach for the domination problem on permutation graphs, The edge inducibility of graphs, The Hamiltonian circuit problem for circle graphs is NP-complete, Achromatic number is NP-complete for cographs and interval graphs, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, A Helly theorem for convexity in graphs, A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs, The complexity of facets (and some facets of complexity), The domatic number problem on some perfect graph families, A setup heuristic for interval orders

Cites Work

• Unnamed Item
• Unnamed Item
• The inducibility of graphs
• A simple proof of the Kruskal-Katona theorem
• The edge inducibility of graphs