Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNonempty intersection of longest paths in $2K_2$-free graphs
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 1966, Gallai asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallais question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, and series-parallel graphs. A graph is $2K_2$-free if it does not contain two independent edges as an induced subgraph. In this paper, we show that in nonempty $2K_2$-free graphs, every vertex of maximum degree is common to all longest paths. Our result implies that all longest paths in a nonempty $2K_2$-free graph have a nonempty intersection. In particular, it gives a new proof for the result on split graphs, as split graphs are $2K_2$-free.
rate research
Read More
Let $P,Q$ be longest paths in a simple graph. We analyze the possible connections between the components of $Pcup Qsetminus (V(P)cap V(Q))$ and introduce the notion of a bi-traceable graph. We use the results for all the possible configurations of the intersection points when $#V(P)cap V(Q)le 5$ in order to prove that if the intersection of three longest paths $P,Q,R$ is empty, then $#(V(P)cap V(Q))ge 6$. We also prove Hippchens conjecture for $kle 6$: If a graph $G$ is $k$-connected for $kle 6$, and $P$ and $Q$ are longest paths in $G$, then $#(V(P)cap V(Q))ge 6$.
We prove that for a connected simple graph $G$ with $nle 10$ vertices, and two longest paths $C$ and $D$ in $G$, the intersection of vertex sets $V(C)cap V(D)$ is a separator. This shows that the graph found previously with $n=11$, in which the complement of the intersection of vertex sets $V(C)cap V(D)$ of two longest paths is connected, is minimal.
A graph is called $2K_2$-free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every $frac{3}{2}$-tough $2K_2$-free graph with at least three vertices has a spanning trail with maximum degree at most $4$. In this paper, we confirm this conjecture. We also provide examples for all $t < frac{5}{4}$ of $t$-tough graphs that do not have a spanning trail with maximum degree at most $4$.
Given integers $k,j$ with $1le j le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the `Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph contains a colourful path on $chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $chi(G)$. Recent work on this conjecture by Gyarfas and Sarkozy, and Scott and Seymour has shown the existence of a function $f$ such that if $chi(G)geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
