<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue2" %>
Generalized Matrogenic Graphs
Igor E. Zverovich
Rutgers Center for Operations Research, Rutgers University, Piscataway, NJ 08854-8003, USA
Annals of Combinatorics 10 (2) p. 285-290 June, 2006
AMS Subject Classification: 05B35, 05C62
Using a forbidden induced subsystem characterization of matroids, we propose a method for characterizing classes of P-matrogenic graphs for all hereditary graph properties P.
Keywords: independence system, matroid, matrogenic graph, forbidden induced subsystem characterization


1. C. Benzaken and P.L. Hammer, Boolean techniques for matroidal decomposition of independence systems and applications to graphs, Discrete Math. 56 (1) (1985) 7–34.

2. G. Ding and P.L. Hammer, Matroids arisen from matrogenic graphs, Discrete Math. 165–166 (1997) 211–217.

3. S. Foldes and P.L. Hammer, On a class of matroid-producing graphs, In: Combinatorics, Vol. I, North-Holland, Amsterdam-New York, (1978) pp. 331–352.

4. S. Foldes and P.L. Hammer, Split graphs, In: Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XIX Utilitas Math., Winnipeg, Man., (1977) pp. 311–315.

5. V. Giakoumakis, On extended P4-sparse graphs, In: 4th Twente Workshop on Graphs and Combinatorial Optimization, (1995), extended abstract.

6. P.L. Hammer and I.E. Zverovich, Splitoids, Graph Theory Notes N. Y. 46 (2004) 36–40.

7. C.T. Hoáng, Perfect graphs, Ph. D. Thesis, McGill University, 1985.

8. N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics, Ann. Discrete Math. Vol 56 North-Holland, Amsterdam, 1995 .

9. P. Mihók, On graphs matroidal with respect to additive hereditary properties, In: Graphs, Hypergraphs and Matroids, II, Higher College Engrg., Zielona Gra, (1987) pp. 53–64

10. U.N. Peled, Matroidal graphs, Discrete Math. 20 (3) (1977/78) 263–286.

11. R.I. Tyshkevich, O.P. Urbanovich, and I.E. Zverovich, Matroidal decomposition of a graph, In: Combinatorics and Graph Theory, Proceedings of 30th Semester 25, Banach Center Publications PWN, Warsaw, (1989) pp. 195–205.

12. J.L. Wu, Forest-inducing independence systems of graphs, Appl. Math. J. Chinese Univ. 6 (3) (1991) 420–426.