Graph connectivity

• Grant number: 20/11118-6
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: March 01, 2021
• End date: August 31, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Orlando Lee
• Grantee: Alonso Ali Gonçalves
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

A graph G = (V,E) is connected if for every pair of vertices u and v in V there is a path from u to v in G; if there isn't, we say that G is disconnected. A graph is k-connected if it has more than k vertices and the removal of any k' < k vertices does not disconnect it.In 1963, Tutte showed that for every 3-connected graph G and any pair of vertices u,v in V(G) there is a path P from u to v such that G - V(P) is connected. Based on Tutte's result, in 1975 Lovász conjectured that for every positive integer k there is a positive integer f(k) such that for every f(k)-connected graph G and vertices u,v in V(G) there is a path P from u to v where G - V(P) is k-connected. Tutte's result proves that f(1)=3. Based on Lovász conjecture, Fernandes, Hernández-Vélez, Lee and Pina proposed the study of paths in spanning trees of a graph G that are non-separating in G. Let G be a graph and T a spanning tree of G. We say that T is a Tutte tree if for any path P in T we have that G - V(P) is connected. Clearly, every Hamiltonian graph has a Tutte tree. In this project, we present the main results about Tutte trees, introduce new results on its existence and propose the study of Tutte trees in hipohamiltonian graphs.In 1984, Itai and Rodeh proposed the concept of independent trees. We say that two trees T' and T'' that are rooted in r are independent if for every vertex x in (V(T') \cap V(T'')) we have that the paths from r to x in T' and T'' are internally disjoint. In 1989, Itai and Zehavi conjectured that for any k-connected graph there are k independent spanning trees rooted on any vertex. This conjecture is known as the Independent Trees Conjecture.Analogously to the concept of independent trees not having paths from the root that share a vertex, Itai and Rodeh proposed edge-independent trees: trees that are rooted in r and whose paths from the root to any vertex in (V(T') \cap V(T'')) are edge-disjoint. The authors conjectured that for any k-edge-connected graph there are k independent spanning trees rooted on any vertex. This conjecture is known as the Edge-Independent Trees Conjecture and, although there is no result on its relation to the Independent Trees Conjecture, many of the existing results on edge-independent trees are clear adaptations from its independent trees counterpart. Both conjectures remain open on cases where k > 4. In this project, we present the main results on Tutte trees and the Independent Trees and Edge-Independent Trees Conjectures and discourse about the problems we will tackle throughout the project. Besides that, we introduce a new problem on Tutte trees and new results on its existence in graphs. (AU)