% 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
	$p<q$ in $\{1,\dots,\ell-1\}$. Then
	$$\{v_0v_1\}\cup\{v_{a+1}v_{a+2}\mid a\le p,\ v_a\in N(x) \}\cup\{ v_bv_{b+1}\mid b\ge q,\ v_b\in N(x)\}\subseteq E(S,T)$$
	is a set of $k+1$ independent edges.
	
	Now, by Lemma~\ref{bi}, there is a vertex $y\in T$ such that $N(y)$ meets all edges in $E(S,T)$. If $|V(P)|\ge 2k+2$, then $y$ has at least $k+1$ neighbors in $V(P)=S\cup T$ since $E(S,T)$ contains an independent set of $k+1$ edges. Then $d(y)\ge k+1>k=\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.

