| dc.description | In 30's Hassler Whitney developed a remarkable theory on graphs and their cycle matroids
[30, 31, 32, 33]. Graphs G = (V;E;ɸ) and G' = (V';E';ɸ') are called strongly isomorphic
if E = E' and there exists a bijection α: V -> V' such that ɸ(e) = {x,y} => ɸ'(e)= ({α (x), α (y)}. One of the problems (W P) Whitney considered and completely solved was
to describe the classes of graphs G having the same cycle matroid M(G) and, in particular,
to describe all graphs G that are uniquely de ned (up to strong isomorphism) by their cycle
matroid M(G). Various strengthenings and extensions of theses results have been found
since then (see, for example, [7, 8, 13, 15, 19]).
In this work we first introduce and study the properties of the series of so-called k-
circular matroids Mk(G) of a graph G (where k is a non-negative integer) such that M0(G)
is the cycle matroid of graph G and M1(G) is the bicircular matroid of graph G. We give
a graph structure characterization of the main constituents of matroid Mk(G) such as the
independent sets, bases, circuits, cocircuits, components, etc.
Next, we consider the analog (WP)k of the Whitney problem (WP), where the cycle matroid
M(G) is replaced by matroid Mk(G). Our above mentioned results on graph structure
characterizations of various ingredients of k-circular matroids provide a natural basis for the
study of problem (WP)k. For k = 1 this problem was solved in [4, 27]. Namely, it was
shown that if graphs G and G' are not strongly isomorphic and M1(G) = M1(G'), then G'
can be obtained from G by a series of some graph operations from a given list of operations
and M1(F) = M1(G) for every intermediate graph F.
In order to extend the Whitney results on problem (WP) to problems (WP)k for k ≥ 2
we introduce a set of operations on graphs that for k ≥ 2 provide not strongly isomorphic
graphs G and G' with the same k-circular matroid. We also obtain (among other things) some
results analogous to Whitney's matroid-isomorphism theorem for 3-connected graphs (when
k = 0) providing a class of graphs that are uniquely de ned (up to strong isomorphism)
by their k-circular matroids. In particular, for every k ≥ 1 we establish an extension of
Whitney's matroid-isomorphism theorem for 3-connected graphs by giving a criterion for a
3-connected graph to be uniquely de ned by its k-circular matroid. | |
