| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313109 |
| ISSN: | 0101-7438 |
| Authors: | Cortez Morales, Walter Julio1 |
| Institutions: | 1Universidade Estadual Paulista "Julio de Mesquita Filho", Instituto de Biociencias, Letras e Ciencias Exatas, Sao Jose do Rio Preto, Sao Paulo. Brasil |
| Year: | 2005 |
| Season: | Ene-Abr |
| Volumen: | 25 |
| Number: | 1 |
| Pages: | 1-9 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Experimental |
| English abstract | This paper is motivated by the result of Berge who generalized Tutte's theorem which states that: Given a graph G with |V(G)| vertices and n(G) the number of edges in a maximum matching, then there is a subset X Í V(G) such that |V(G)|+|X| - w(G\X) - 2n( G)=0, where w(G\X) denotes the number of odd components of G\X, such expression is called Tutte-Berge's equation associated to G, denoted by T(G;X)=0. These graphs are then studied from solutions of T(G;X)=0. A graph G is called immersible graph if and only if, its associated equation T(G;X)=0 has at least one non-emptyset for X, and it is non-immersible graph if and only if, the unique solution to T(G;X)=0 is the emptyset. The main result of this work is the characterization of immersible graphs via complete antifactor sets, moreover we prove that factorizable graphs are included in the class of immersible graphs |
| Portuguese abstract | Este trabalho é motivado pelo resultado de Berge, que é uma generalização do teorema de Tutte o qual expressamos na forma: Dado o grafo G de ordem |V(G)| e n(G) o número de arestas em um emparelhamento máximo, existe um conjunto X de vértices de G tal que |V(G)|+|X| - w(G\X) - 2n(G)=0, onde w(G\X) é o número de componentes de ordem ímpar de G\X. Tal expressão chamamos a equação de Tutte-Berge associada de G, e escrevemos simplesmente T(G; X)=0. Os grafos podem ser classificados a partir das soluções da equação de Tutte-Berge. Um grafo G é chamado imersível se, e somente se, T(G; X)=0 possui pelo menos um conjunto solução não vazio de vértices, e G é denominado não imersível se, e somente se, o conjunto vazio é a única solução de T(G; X)=0. O resultado principal deste artigo é a caracterização de grafos imersíveis pelos conjuntos antifatores completos, além disso, provamos que os grafos fatoráveis estão contidos na classe dos imersíveis |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Teoría de grafos, Grafos inmersibles, Grafos factorables, Antifactor completo, Ecuación de Tutte-Berge |
| Keyword: | Mathematics, Applied mathematics, Graph theory, Immersible graphs, Factorizable graphs, Complete antifactor, Tutte-Berge equation |
| Full text: | Texto completo (Ver HTML) |
