On graphs uniquely defined by their \(K\)-circular matroids. (English) Zbl 1358.05047
Summary: H. Whitney [Amer. J. Math. 54, 150–168 (1932; JFM 58.0609.01); ibid. 55, 245–254 (1933; JFM 59.1235.01); ibid. 57, 509–533 (1935; JFM 61.0073.03)] considered and completely solved the problem (WP) of describing the classes of graphs \(G\) having the same cycle matroid \(M(G)\). A natural analog (WP)\(^\prime\) of Whitney’s problem (WP) is to describe the classes of graphs \(G\) having the same matroid \(M^\prime(G)\), where \(M^\prime(G)\) is a matroid (on the edge set of \(G\)) distinct from \(M(G)\). For example, the corresponding problem \((\mathrm{WP})^\prime = (\mathrm{WP})_\theta\) for the so-called bicircular matroid \(M_\theta(G)\) of graph \(G\) was solved in C. R. Coulard et al. [Discrete Appl. Math. 32, No. 3, 223–240 (1991; Zbl 0755.05025)] and D. K. Wagner [J. Comb. Theory, Ser. B 39, 308–324 (1985; Zbl 0584.05019)]. The authors [“\(K\)-circular matroids of graphs”, Preprint, arXiv:1508.05364] introduced and studied the so-called \(k\)-circular matroids \(M_k(G)\) for every non-negative integer \(k\) that is a natural generalization of the cycle matroid \(M(G) := M_0(G)\) and of the bicircular matroid \(M_\theta(G) : = M_1(G)\) of graph \(G\). In this paper (which is a continuation of our paper De Jesús and Kelmans [loc. cit.]) we establish some properties of graphs guaranteeing that the graphs are uniquely defined by their \(k\)-circular matroids.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
Keywords:
vertex star; bicycle; cacti-graph; matroid; \(k\)-circular matroid; non-separating cocircuitReferences:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer-Verlag: Springer-Verlag New York, 3rd Corrected Printing, GTM 244 · Zbl 1134.05001 |
| [2] | Coulard, C. R.; del Greco, J. G.; Wagner, D. K., Representations of bicircular matroids, Discrete Appl. Math., 32, 223-240 (1991) · Zbl 0755.05025 |
| [3] | Diestel, R., Graph Theory (2000), Springer-Verlag: Springer-Verlag New York · Zbl 0945.05002 |
| [4] | Halin, R.; Jung, H. A., Note on isomorphisms of graphs, J. Lond. Math. Sec., 42, 254-256 (1967) · Zbl 0147.42703 |
| [5] | Hemminger, R. L.; Jung, H. A.; Kelmans, A. K., On 3-skein isomorphisms of a graph, Combinatorica, 2, 4, 373-376 (1982) · Zbl 0513.05034 |
| [8] | Kelmans, A. K., The concept of a vertex in a matroid, the non-separating cycles and a new criterion for graph planarity, (Algebraic Methods in Graph Theory, Vol. 1, Colloq. Math. Soc. János Bolyai, (Szeged, Hungary, 1978), 25 (1981), North-Holland), 345-388 · Zbl 0494.05036 |
| [9] | Kelmans, A. K., On 3-skeins in a 3-connected graph, Studia Sci. Math. Hungar., 22, 265-273 (1987) · Zbl 0648.05037 |
| [10] | Kelmans, A. K., On semi-isomorphisms and semi-dualities of graphs, Graphs Combin., 10, 337-352 (1994) · Zbl 0814.05059 |
| [11] | Oxley, J. G., Matroid Theory (2006), Oxford University Press · Zbl 1115.05001 |
| [12] | Wagner, D. K., Connectivity in bicircular matroids, J. Combin. Theory Ser. B, 39, 308-324 (1985) · Zbl 0584.05019 |
| [13] | Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002 |
| [14] | Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 159-168 (1932) · JFM 58.0609.01 |
| [15] | Whitney, H., Non-separable and planar graphs, Amer. J. Math., 34, 339-362 (1932) · JFM 58.0608.01 |
| [16] | Whitney, H., 2-isomorphic graphs, Amer. J. Math., 55, 245-254 (1933) · JFM 59.1235.01 |
| [17] | Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533 (1935) · JFM 61.0073.03 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
