اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinimal graph in which the intersection of two longest paths is not a separator
176
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 $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 th
e 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 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 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 fol
iations 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 wit
h 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
