Conuco Ver 2.2
Índice de Puerto Rico
Conuco Ver 2.2
Índice de Puerto Rico

Información del Artículo

K-Circular matroids of graphs and extensions of whitney's theory on matroid isomorphism of graphs / José F. De Jesús Rosa, Alexander Kelmans
En: Mar. 2015: p 1-97. bibl. graf.
Revista: Sitio en Internet
Resumen: Resumen en español
Resumen: 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.
Palabras Claves: Whitney, k-circular matroids, matroid isomorphism, unique representation, mathematics
Areas Temáticas:

 Ver Formato MARC  |  Email Record  |    | 
  © 2017 Copyright CONUCO 2.2
Powered by Indices Conuco,
P O Box 7067
Caguas PR 00726
Octafish Media