INVESTIGADORES
BONOMO flavia
congresos y reuniones científicas
Título:
On fractional graph and hypergraph isomorphism and its applications
Autor/es:
BONOMO, FLAVIA; TILLI, DORA
Lugar:
La Plata
Reunión:
Workshop; VII Latin-American Workshop on Cliques in Graphs; 2016
Institución organizadora:
UNLP
Resumen:
Fractional isomorphism of graphs is the linear relaxation of an integerprogramming formulation of graph isomorphism. It preserves some invariantsof graphs, but it does not preserve others like connectivity, cliquenumber, chromatic number, and matching number.In this work, we extend the concept of fractional isomorphism of graphsto hypergraphs, and give alternative characterizations, analogous to thosethat are known for graphs. With this new concept we prove that the fractionalpacking and covering numbers on hypergraphs are invariant underfractional hypergraph isomorphism, and as a consequence we prove that fractionalmatching is invariant under fractional graph isomorphism.We also study the validity of an analogous to Whitney?s theorem for linegraphs applied to fractional isomorphism, thus obtaining partial resultsin this direction.
