
Título: 
KCircular matroids of graphs and extensions of whitney's theory on matroid isomorphism of graphs / José F. De Jesús Rosa, Alexander Kelmans

Autores: 

En: 
Mar. 2015: p 197. bibl. graf.

URL: 

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 socalled k circular matroids Mk(G) of a graph G (where k is a nonnegative 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 kcircular 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 kcircular matroid. We also obtain (among other things) some results analogous to Whitney's matroidisomorphism theorem for 3connected graphs (when k = 0) providing a class of graphs that are uniquely de ned (up to strong isomorphism) by their kcircular matroids. In particular, for every k ≥ 1 we establish an extension of Whitney's matroidisomorphism theorem for 3connected graphs by giving a criterion for a 3connected graph to be uniquely de ned by its kcircular matroid.

Palabras Claves: 
Whitney, kcircular matroids, matroid isomorphism, unique representation, mathematics

Areas Temáticas: 


LDR 03298cab a2200290 a 4500 001 11191789 003 20150423 14:34:09.0 005 20150423 14:34:38.0 008 153423t2012uuuupr esp d 040 $aCI 082 00$aTérmino clasificatorio 245 00$aKCircular matroids of graphs and extensions of whitney's theory on matroid isomorphism of graphs /$cJosé F. De Jesús Rosa, Alexander Kelmans 260 $cMar. 2015: p 197. bibl. graf. 440 00$aSitio en Internet 504 $aWhitney, kcircular matroids, matroid isomorphism, unique representation, mathematics 520 0 $aResumen en español 520 a$aIn 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 socalled k circular matroids Mk(G) of a graph G (where k is a nonnegative 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 kcircular 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 kcircular matroid. We also obtain (among other things) some results analogous to Whitney's matroidisomorphism theorem for 3connected graphs (when k = 0) providing a class of graphs that are uniquely de ned (up to strong isomorphism) by their kcircular matroids. In particular, for every k ≥ 1 we establish an extension of Whitney's matroidisomorphism theorem for 3connected graphs by giving a criterion for a 3connected graph to be uniquely de ned by its kcircular matroid. 700 10$aDe Jesús Rosa, José F. 700 10$aKelmans, Alexander 856 78$uhttp://repositorio.upr.edu:8080/jspui/bitstream/10586%20/535/1/Thesis%20Doctoral%20Degree%20Jose%20F.%20De%20Jesus%20S.pdf 949 a$aacgr
