Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimal graph in which the intersection of two longest paths is not a separator
176
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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$.
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.
We exhibit a pseudogroup of smooth local transformations of the real line which is compactly generated, but not realizable as the holonomy pseudogroup of a foliation of codimension 1 on a compact manifold. The proof relies on a description of all foliations with the same dynamic as the Reeb component.
Let $f(n,H)$ denote the maximum number of copies of $H$ possible in an $n$-vertex planar graph. The function $f(n,H)$ has been determined when $H$ is a cycle of length $3$ or $4$ by Hakimi and Schmeichel and when $H$ is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determine $f(n,H)$ exactly in the case when $H$ is a path of length 3.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
