اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBi-traceable graphs, the intersection of three longest paths and Hippchens conjecture
72
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 s
plit 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 $G$ be a $k$-connected graph on $n$ vertices. Hippchens Conjecture states that two longest paths in $G$ share at least $k$ vertices. Gutierrez recently proved the conjecture when $kleq 4$ or $kgeq frac{n-2}{3}$. We improve upon both results; name
ly, we show that two longest paths in $G$ share at least $k$ vertices when $k=5$ or $kgeq frac{n+2}{5}$. This completely resolves two conjectures of Gutierrez in the affirmative.
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 compl
ement of the intersection of vertex sets $V(C)cap V(D)$ of two longest paths is connected, is minimal.
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 deter
mine 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 apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to the
m, and the structure theorems and reducibility results are of independent interest.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
