% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.37}{25(2)}{2018} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%Packges for this paper %%%%%%%%%%%%%%%%%%% \usepackage{amsfonts} %\usepackage{fontenc} \usepackage{graphicx,psfrag} \usepackage{subcaption} \usepackage{tkz-graph} \usetikzlibrary{arrows} \usepackage{tkz-euclide} \usetkzobj{all} %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Nov 21, 2017}{May 1,2018}{Jun 8, 2018} %\MSC{05C38} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05C38} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} \Copyright{The authors. Released under the CC BY license (International 4.0).} %\Copyright{The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{Nonempty intersection of longest\\ paths in $2K_2$-free graphs} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \author{Gili Golan \qquad Songling Shan\\ \small Department of Mathematics\\[-0.8ex] \small Vanderbilt University\\[-0.8ex] \small Nashville, TN, U.S.A.\\ \small\tt \{gili.golan,songling.shan\}@vanderbilt.edu} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} In 1966, Gallai asked {\it whether all longest paths in a connected graph share a common vertex}. Counterexamples indicate that this is not true in general. However, Gallai's 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 short note, 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 strengthens the result on split graphs, as split graphs are $2K_2$-free. \end{abstract} \section{Introduction} All graphs considered in this paper are finite and simple. A path $P$ in a graph $G$ is a \emph{longest path} in $G$ if there is no path in $G$ strictly longer than $P$. In 1966 Gallai asked \cite{Gallai} whether all longest paths in a connected graph have a vertex in common. In 1974, Walther~\cite{Walther69} gave a counterexample to the problem. As every hypo-traceable graph (i.e., a graph with no Hamiltonian path where all vertex-deleted subgraphs admit a Hamiltonian path) is clearly a counterexample, there are infinitely many counterexamples to the problem (see Thomassen~\cite{Thomassen76}). In spite of the negative answer for general graphs, the answer to Gallai's problem when restricted to many classes of graphs is positive. Klav\v{z}ar and Petkov\v{s}ek~\cite{KlavzarP90} gave an affirmative answer to Gallai's question for connected split graphs and for cacti. An affirmative answer for the class of connected circular-arc graphs was given by Balister et al.~\cite{BalisterGLS04} (see also Joos~\cite{MR3368978}). A positive answer for connected outerplanar graphs and 2-trees was given by de Rezende et al.~\cite{Eurocomb11}. Recently, the second author with Chen et al.~\cite{Chen2017287} extended this result, giving a positive solution to Gallai's problem for the class of connected series-parallel graphs. For more information about Gallai's problem and several variations, see \cite{MR3093252}. In this paper, we investigate the intersection of all longest paths in connected $2K_2$-free graphs. A graph is {\it $2K_2$-free} if it contains no two independent edges as an induced subgraph. The class of $2K_2$-free graphs is well studied, for instance, see~\cite{ CHUNG1990129, MR2279069, MR1172684}. It contains the class of {\it split graphs\/}, where vertices can be partitioned into a clique and an independent set. One can also easily check that every {\it cochordal\/} graph (i.e., a graph that is the complement of a chordal graph) is $2K_2$-free and so the class of $2K_2$-free graphs is at least as rich as the class of chordal graphs. In this note we prove the following. \begin{theorem}\label{thm1} In a nonempty $2K_2$-free graph, every vertex of maximum degree is common to all longest paths. \end{theorem} In particular, the answer to Gallai's problem is positive for $2K_2$-free graphs. Theorem~\ref{thm1} also strengthens Klav\v{z}ar and Petkov\v{s}ek's result for split graphs ~\cite{KlavzarP90}. \begin{corollary}\label{thm2} If $G$ is a nonempty split graph or cochordal graph, then every vertex of maximum degree is common to all longest paths. \end{corollary} We note that Theorem \ref{thm1} is best possible in terms of the number of copies of $K_2$ in the forbidden subgraph. Indeed, in connected $3K_2$-free graphs a vertex of maximum degree does not necessarily belong to the intersection of all longest paths. For example, consider the graph in Figure \ref{graph}. It is $3K_2$-free; the top vertex is of maximum degree but does not belong to the longest path passing through all the remaining vertices. \begin{figure} \captionsetup{justification=centering,margin=2cm} \begin{center} \begin{tikzpicture}[thick, scale=0.6] \draw [black, thick] (-9,0) -- (-7,0)--(-5,0)--(-3,0)--(-1,0)--(1,0)--(3,0)--(5,0)--(7,0)--(9,0); \draw [black, thick] (0,3)--(-5,0); \draw [black, thick] (0,3)--(-1,0); \draw [black, thick] (0,3)--(3,0); \draw [black, thick] (0,3)--(7,0); \draw [black,thick] (-7,0) to [out=-60,in=-120] (-1,0); \draw[black,thick] (-7,0) to [out=-60,in=-120] (3,0); \draw[black,thick] (-5,0)to [out=-60,in=-120] (7,0); %\draw[black, thick](-1,0)--(0,1)--(1,0); \filldraw [black] (-9,0) circle (3pt); \filldraw [black] (-7,0) circle (3pt); \filldraw [black] (-5,0) circle (3pt); \filldraw [black] (-3,0) circle (3pt); \filldraw [black] (-1,0) circle (3pt); \filldraw [black] (1,0) circle (3pt); \filldraw [black] (3,0) circle (3pt); \filldraw [black] (5,0) circle (3pt); \filldraw [black] (7,0) circle (3pt); \filldraw [black] (9,0) circle (3pt); \filldraw [black] (0,3) circle (3pt); \end{tikzpicture} \end{center} \caption{ A $3K_2$-free graph with a vertex of maximum degree not belonging to every longest path. \label{graph} } \end{figure} For a graph $G$ we will denote by $V(G)$ and $E(G)$ the vertex set and edge set of $G$, respectively. If $uv\in E(G)$, we write $u\sim v$ to denote the adjacency of $u$ and $v$. For two disjoint subsets $S, T\subseteq V(G)$, we denote by $E_G(S,T)$ the set of edges of $G$ with one end in $S$ and the other in $T$. If $u\in V(G)$, we denote by $N_G(u)$ the set of neighbors of $u$ in $G$. If $G$ is clear from the context, we omit the subscript $G$ and write $E(S,T)$ and $N(u)$. \section{Proof of Theorem~\ref{thm1}} In this section we prove Theorem~\ref{thm1}. We will need the following three lemmas. A path $P$ in a graph $G$ is {\it dominating} if $G-V(P)$ is edgeless. \begin{lemma}\label{dom} Let $G$ be a $2K_2$-free graph. Then every longest path in $G$ is dominating. \end{lemma} \begin{proof} Let $P=v_0v_1\cdots v_{\ell}$ be a longest path in $G$. Assume by contradiction that $P$ is not dominating. Then there exists an edge $uv\in E(G)$ such that $u,v\notin V(P)$. % Let $v_0$ be an endpoint of $P$ and $v_0v_1\in E(P)$. Since $G$ is $2K_2$-free, there must be an edge $e'$ in $G$ which connects the edge $uv$ to the edge $v_0v_1$. Without loss of generality, we can assume that $e'$ connects $v$ to either $v_0$ or $v_1$. If $e'=vv_0$ then $uvv_0v_1\cdots v_{\ell}$ is a path in $G$ longer than $P$. If $e'=vv_1$ then $uvv_1\cdots v_{\ell}$ is a path in $G$ longer than $P$. \end{proof} The proof of the following lemma follows from standard arguments. \begin{lemma}\label{4} Let $G$ be a graph. Let $P=v_0v_1\cdots v_{\ell}$ be a longest path in $G$ and let $x$ be a vertex of $G$ which does not belong to $P$. Then the following assertions hold. \begin{enumerate} \item[(1)] The vertex $x$ is not adjacent to the endpoints $v_0$ and $v_{\ell}$ of $P$. \item[(2)] The vertex $x$ does not have two neighbors which are consecutive vertices $v_i,v_{i+1}$ on~$P$. \item[(3)] If $v_a$ is a neighbor of $x$ then $v_0$ is not adjacent to $v_{a+1}$. \item[(4)] If $v_a$ and $v_b$ are distinct neighbors of $x$ then $v_{a+1}$ is not adjacent to $v_{b+1}$. \end{enumerate} \end{lemma} The following lemma was proved in~\cite[Theorem 1]{CHUNG1990129}. \begin{lemma}\label{bi} Let $G$ be a nonempty $2K_2$-free graph and let $S\subseteq V(G)$ be an independent set. Let $T\subseteq V(G)-S$. Then there exists $y\in T$ such that $N(y)$ meets all edges in $E(S,T)$. \end{lemma} \begin{proof}[Proof of Theorem \ref{thm1}] Let $G$ be a nonempty $2K_2$-free graph and let $P=v_0v_1\cdots v_{\ell}$ be a longest path in $G$. Assume that $x\in V(G)$ is a vertex of maximum degree in $G$ which does not belong to $P$. Let $k=d(x)=\Delta(G)$. By Lemma~\ref{dom}, $N(x)\subseteq V(P)$. Let $$S=\{v_0, v_{a+1}\mid v_a\in N(x)\}\subseteq V(P).$$ By (3) and (4) of Lemma~\ref{4}, $S$ is an independent set. Let $T=V(P)-S$. By (1) and (2) of Lemma~\ref{4}, $V(P)$ contains at least $2k+1$ vertices. %If $|V(p)|=2k+1$, then The set $\{v_av_{a+1}\mid v_a\in N(x)\}$ is a set of $k$ independent edges in $E(S,T)$ (i.e., $k$ edges which pairwise do not share an endpoint). We claim that if $|V(P)|\ge 2k+2$ then there are $k+1$ independent edges in $E(S,T)$. Indeed, the $k$ neighbors of $x$ separate $P$ into $k+1$ non-trivial subpaths (see Lemma~\ref{4}(1)). By the pigeonhole principle one of these subpaths contains at least two vertices in $V(P)-N(x)$. If $v_0$ is an endpoint of this subpath, then $v_0,v_1\notin N(x)$ and $$\{v_0v_1,v_av_{a+1}\mid v_a\in N(x)\}\subseteq E(S,T)$$ is an independent subset of $k+1$ edges. If $v_{\ell}$ is an endpoint of this subpath then $$\{v_0v_1,v_{a+1}v_{a+2}\mid v_{a}\in N(x)\}\subseteq E(S,T)$$ is an independent subset of size $k+1$. Thus, we can assume that the endpoints of this subpath are $v_p,v_q\in N(x)$ for some $pk=\Delta(G)$, a contradiction. If $|V(P)|=2k+1$ then $T=N(x)$. Indeed, the disjoint union $S\cup N(x)\subseteq V(P)$ and $|S|=k+1$, $|N(x)|=k$. Hence $N(x)=V(P)-S=T$. In particular, in that case, $y\in N(x)$. Since $N(y)$ meets all edges in $E(S,T)$ and $E(S,T)$ contains an independent set of $k$ edges, $y$ has at least $k$ neighbors in $V(P)$. Since $x$ is also a neighbor of $y$ we have $d(y)\ge k+1>k=\Delta(G)$, a contradiction. \end{proof} \section*{Acknowledgements} The authors would like to thank Guantao Chen and Akira Saito for their helpful discussions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % You do not have to use the same format for your references, but % include everything in this file. Don't use natbib please. % If you use BibTeX to create a bibliography, copy the .bbl file into here. \begin{thebibliography}{99} \bibitem{BalisterGLS04} P.~N. Balister, E.~Gy{\H o}ri, J.~Lehel, and R.~H. Schelp. \newblock Longest paths in circular arc graphs. \newblock \emph{Combinatorics, Probability and Computing}, 13(3): 311--317, 2004. \bibitem{Chen2017287} G. Chen, J. Ehrenm{\"u}ller, C.~G. Fernandes, C.~G. Heise, S. Shan, P. Yang, and A.~N. Yates. \newblock Nonempty intersection of longest paths in seriesparallel graphs. \newblock \emph{Discrete Mathematics}, 340(3):287--304, 2017. \bibitem{CHUNG1990129} F.~R.~K. Chung, A.~Gy{\'a}rf{\'a}s, Z.~Tuza, and W.~T. Trotter. \newblock The maximum number of edges in {$2K_2$}-free graphs of bounded degree. \newblock \emph{Discrete Mathematics}, 81(2):129--135, 1990. \bibitem{Eurocomb11} S.~F. {de Rezende}, C.~G. Fernandes, D.~M. Martin, and Y.~Wakabayashi. \newblock{Intersection of longest paths in a graph}. \newblock\emph {Electronic Notes in Discrete Mathematics}, 38: 743--748, 2011. \bibitem{Gallai} P.~Erd\H{o}s and G.~Katona~(eds.), \emph{Theory of graphs}. \newblock Proceedings of the Colloquium held at Tihany, Hungary, September 1966. \newblock Academic Press, New York, Problem 4 (T. Gallai), p. 362, 1968. \bibitem{MR3368978} F. Joos. \newblock {A note on longest paths in circular arc graphs}. \newblock\emph{Discuss. Math. Graph Theory}, 35(3):419--426, 2015. \bibitem{KlavzarP90} S.~Klav{\v z}ar and M.~Petkov{\v s}ek. \newblock{Graphs with nonempty intersection of longest paths}. \newblock\emph {Ars Combinatoria}, 29:43--52, 1990 \bibitem{MR2279069} D.~Meister. \newblock{Two characterisations of minimal triangulations of {$2K_2$}-free graphs}. \newblock\emph{Discrete Mathematics}, 306(24):3327--3333, 2006. \bibitem{MR1172684} M.~Paoli, G.~W. Peck, W.~T. Trotter, Jr., and D.~B. West. \newblock{Large regular graphs with no induced {$2K_2$}}. \newblock\emph{ Graphs Combin.}, 8(2):165--197, 1992. \bibitem{MR3093252} A. Shabbir, C.~T. Zamfirescu, and T.~I. Zamfirescu. \newblock{Intersecting longest paths and longest cycles: a survey}, \newblock\emph {Electron. J. Graph Theory Appl. (EJGTA)}, 1(1):56--76, 2013. \bibitem{Thomassen76} C.~Thomassen. \newblock{Planar and infinite hypohamiltonian and hypotraceable graphs}, \newblock\emph {Discrete Mathematics}, 14(4):377--389, 1976. \bibitem{Walther69} H.~Walther. \newblock{\"{U}ber die {N}ichtexistenz eines {K}notenpunktes, durch den alle l\"angsten {W}ege eines {G}raphen gehen}. \newblock\emph {Journal of Combinatorial Theory}, 6:1--6, 1969. \end{thebibliography} \end{document} \bibitem{Bollobas} B. Bollob{\'a}s. \newblock Almost every graph has reconstruction number three. \newblock \emph{J. Graph Theory}, 14(1):1--4, 1990. \bibitem{BH} J.~A. Bondy and R. Hemminger, \newblock Graph reconstruction---a survey. \emph{J. Graph Theory}, 1:227--268, 1977. \doi{10.1002/jgt.3190010306}. \bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary. \newblock A simpler counterexample to the reconstruction conjecture for denumerable graphs. \newblock \emph{J. Combinatorial Theory, Ser. B}, 12:203--204, 1972. \bibitem{HHRT} E. Hemaspaandra, L.~A. Hemaspaandra, S.~P. Radziszowski, and R. Tripathi. \newblock Complexity results in graph reconstruction. \newblock \emph{Discrete Appl. Math.}, 155(2):103--118, 2007. \bibitem{Kelly} P.~J. Kelly. \newblock A congruence theorem for trees. \newblock \emph{Pacific J. Math.}, 7:961--968, 1957. \bibitem{KSU} M. Kiyomi, T. Saitoh, and R. Uehara. \newblock Reconstruction of interval graphs. \newblock In \emph{Computing and combinatorics}, volume 5609 of \emph{Lecture Notes in Comput. Sci.}, pages 106--115. Springer, 2009. \bibitem{Stockmeyer} P.~K. Stockmeyer. \newblock The falsity of the reconstruction conjecture for tournaments. \newblock \emph{J. Graph Theory}, 1(1):19--25, 1977. \bibitem{Ulam} S.~M. Ulam. \newblock \newblock {A collection of mathematical problems}. \newblock Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960. \bibitem{WS} D.~B. West and H. Spinoza. \newblock Reconstruction from $k$-decks for graphs with maximum degree~2. \newblock \arxiv{1609.00284vi}, 2016.