PDF

Discussiones Mathematicae Graph Theory 30(3) (2010) 437-447
DOI: https://doi.org/10.7151/dmgt.1505

GRAPHS FOR n-CIRCULAR MATROIDS

Renata Kawa

Institute of Mathematics, University of Silesia
Bankowa 14, 40-007 Katowice, Poland
e-mail: renia.kawa@wp.pl

Abstract

We give "if and only if" characterization of graphs with the following property: given n ≥ 3, edges of such graphs form matroids with circuits from the collection of all graphs with n fundamental cycles. In this way we refer to the notion of matroidal family defined by Simões-Pereira [2].

Keywords: matroid, matroidal family.

2010 Mathematics Subject Classification: Primary 05B35,
Secondary 05C75.

References

[1]	H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935) 509-533, doi: 10.2307/2371182.
[2]	J.M.S. Simões-Pereira, On matroids on edge sets of graphs with connected subgraphs as circuits II, Discrete Math. 12 (1975) 55-78, doi: 10.1016/0012-365X(75)90095-3.
[3]	J.M.S. Simões-Pereira, Matroidal Families of Graphs, in: N. White (ed.) Matroid Applications (Cambridge University Press, 1992), doi: 10.1017/CBO9780511662041.005.
[4]	J.G. Oxley, Matroid Theory (Oxford University Press, 1992).
[5]	L.R. Matthews, Bicircular matroids, Quart. J. Math. Oxford 28 (1977) 213-228, doi: 10.1093/qmath/28.2.213.
[6]	T. Andreae, Matroidal families of finite connected nonhomeomorphic graphs exist, J. Graph Theory 2 (1978) 149-153, doi: 10.1002/jgt.3190020208.
[7]	R. Schmidt, On the existence of uncountably many matroidal families, Discrete Math. 27 (1979) 93-97, doi: 10.1016/0012-365X(79)90072-4.
[8]	J.L. Gross and J. Yellen, Handbook of Graph Theory (CRC Press, 2004).

Received 16 July 2009
Revised 24 August 2009
Accepted 1 September 2009