
\documentclass[12pt]{article}

\usepackage{e-jc}
\specs{P3.33}{22(3)}{2015}

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{epsfig, float}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\def \nsp {\vspace{-.5ex}}
\def \nspp {\vspace{-2ex}}

\newcommand{\turan}[1]{{\overline t}_{n,#1}}

\newtheorem{Theorem}{Theorem}
\newtheorem{lem}[Theorem]{Lemma}
\newtheorem{defi}{Definition}
\newtheorem{crl}[Theorem]{Corollary}
\newtheorem{prp}[Theorem]{Proposition}
\newtheorem{prm}[Theorem]{Problem}
\newtheorem{rmk}[Theorem]{Remark}
\newtheorem{xmp}[Theorem]{Example}
\newtheorem{obs}[Theorem]{Observation}

\def \taut {\tau_\vartriangle}
\def \nut {\nu_\vartriangle}

\def \bo {\begin{obs} \ }
\def \eo {\end{obs}}

\def \boc {\begin{obs}}
\def \eoc {\end{obs}}

\def \bp {\begin{prp} \ }
\def \ep {\end{prp}}

\def \bpm {\begin{prm} \ }
\def \epm {\end{prm}}

\def \bc {\begin{crl} \ }
\def \ec {\end{crl}}

\def \thm {\begin{Theorem} \ }
\def \ethm {\end{Theorem}}

\def \bl {\begin{lem} \ }
\def \el {\end{lem}}

\def \bd {\begin{defi} \ \rm }
\def \ed {\end{defi}}

\def \brm {\begin{rmk} \ }
\def \erm {\end{rmk}}

\def \bxm {\begin{xmp} \ \rm }
\def \exm {\end{xmp}}

\def \nmr {\begin{enumerate}}
\def \enmr {\end{enumerate}}

\def \tmz {\begin{itemize}}
\def \etmz {\end{itemize}}

\def \smin {\setminus}
\def \nin {\noindent}
\def \bsk {\bigskip}
\def \msk {\medskip}
\def \ssk {\smallskip}
\def \pf {\nin{\bf Proof.} \ }
\def \prf {\nin{\it Proof.} \ }
\def \qed {\hfill $\Box$}
\def \vp {\varphi}
\def \NP {{\sf NP}}
\def \npc {\NP-complete}
\def \kp {\,:\,}
\def \pv {\,;\,}
\def \str {$(\star)$}
\def \taut {\tau_\vartriangle}
\def \nut {\nu_\vartriangle}

\def\cH{{\cal H}}
\def\cC{{\cal C}}
\def\cK{{\cal K}}
\def\cE{{\cal E}}
\def\cF{{\cal F}}
\def\cG{{\cal G}}
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cT{{\cal T}}
\def\cO{{\cal O}}

\def \komm {\LARGE \sf}
\def \ZS {{\LARGE \sf \ ZS \ }}

\newtheorem{claim}{Claim}

\def \bcl {\begin{claim} \ }
\def \ecl {\end{claim}}

\newtheorem{con}{Condition}

\def \bcon {\begin{con} \ \rm }
\def \econ {\end{con}}

\def\T{\mathcal{T}}
\def \dia {\hfill $\Diamond$}

\title{
 Generalized line graphs:\\
  Cartesian products and complexity of recognition
  \thanks{Partially supported by University Grants Commission, India under the grant MRP(S)-0843/13-14/KLMG043/UGC-SWRO,
  Hungarian Scientific Research Fund, OTKA grant 81493 and Hungarian State and the European Union under the grant
TAMOP-4.2.2.A-11/1/ KONV-2012-0072.}}

\author{
Aparna Lakshmanan S.\\
\small Department of Mathematics\\[-0.8ex]
\small St. Xavier's College for Women\\[-0.8ex]
\small Aluva, India\\
\small\tt aparnaren@gmail.com\\
\and Csilla Bujt\'{a}s\\
\small Department of Computer Science and Technology\\[-0.8ex]
\small University of Pannonia\\[-0.8ex]
\small Veszpr\'{e}m,  Hungary\\
\small\tt bujtas@dcs.uni-pannon.hu\\
\and
Zsolt Tuza\\
\small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex]
\small Hungarian Academy of Sciences\\[-0.8ex]
\small Budapest,  Hungary\\
\small\tt tuza@dcs.uni-pannon.hu
 }

 \date{\dateline{Dec 21, 2014}{Aug 20, 2015}{Sep 11, 2015}\\
\small Mathematics Subject Classifications: 05C75 (primary),  05C62, 68Q17}



 \begin{document}

 \maketitle

\vspace*{-\baselineskip}
\begin{abstract}
   Putting the concept of line graph in a more general setting, for a positive integer $k$ the
  $k$-line graph $L_k(G)$ of a graph $G$ has the $K_k$-subgraphs of
  $G$ as its vertices, and two vertices of $L_k(G)$ are adjacent if
  the corresponding copies of $K_k$ in $G$ share $k-1$ vertices.
     Then, 2-line graph is just the line graph in  usual
   sense, whilst 3-line graph is also known as triangle graph.
   The $k$-anti-Gallai graph $\triangle_k(G)$ of $G$
   is a  specified subgraph of $L_k(G)$ in which two vertices are
   adjacent if the corresponding two $K_k$-subgraphs are contained in a common
   $K_{k+1}$-subgraph in $G$.

We give a unified characterization for nontrivial connected graphs
$G$ and $F$ such that the Cartesian product $G\mathop{\Box} F$ is a
$k$-line graph. In particular  for $k=3$, this answers the
question of Bagga (2004), yielding the necessary and sufficient
condition that $G$ is the line graph of a triangle-free  graph and
$F$  is a complete graph (or vice versa). We show that for any
$k\ge 3$, the $k$-line graph of a connected graph $G$ is
isomorphic to the line graph of $G$ if and only if $G=K_{k+2}$.
Furthermore, we prove that the recognition problem  of $k$-line
graphs and that of $k$-anti-Gallai graphs are {\sf NP}-complete
for each $k\ge 3$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Triangle graph, $k$-line graph,
anti-Gallai graph, Cartesian product graph.
\end{abstract}



 \section{Introduction}


 The   line graph $L(G)$ of a graph $G$ has
   vertices representing the edges ($K_2$-subgraphs) of $G$
 and two vertices in the line graph are adjacent
  if and only if the corresponding
 edges share a vertex (a $K_1$ subgraph) in $G$. The analogous
 notion in the dimension higher by one is the triangle graph
 $\cT(G)$ of $G$ whose  vertices correspond to the triangles
 ($K_3$-subgraphs) of $G$ and the vertices representing triangles
 having a common  edge ($K_2$-subgraph) are adjacent. The natural
 generalization gives the notion of $k$-line graph, which
 together with its specified subgraph, the so-called $k$-anti-Gallai
 graph is the  main subject of this paper.

 \subsection{Terminology}

All graphs considered here are simple and undirected.
 The vertex set and the edge set of a graph $G$ are denoted by
 $V(G)$ and $E(G)$, respectively.
   Throughout this paper, a {\it $k$-clique} of $G$ will be
meant as a complete $K_k \subseteq G$
 subgraph. That is,  \emph{inclusion-wise  maximality is
 not required}. For the sake of simplicity, if the meaning is clear
  from the context,
 we do not distinguish between a clique and its
 vertex set in notation (e.g., the
 vertex set of a clique $C$ will also be denoted by $C$ instead of
 $V(C)$). The \emph{clique number} $\omega(G)$
 is the maximum order of a clique contained in $G$.
  The {\it Cartesian product} of two graphs $G$ and $F$,
denoted by $G \Box F$, has the ordered pairs $(u,v)$
 as its vertices where $u \in
V(G)$ and $v \in V(F)$, and two vertices $(u,v)$ and $(u',v')$
are adjacent if $u  = u'$ and $v $ is adjacent to $v'$ or $v = v'$
and $u$ is adjacent to $u'$.
  If $v_i \in V(F)$, the {\it copy\/} $G_i$ is the subgraph of $G\mathop{\Box} F$
  induced by  the vertex set
 $V(G_i)=\{(u_j,v_i): u_j \in V(G)\}$.
The copy $F_j$ for $u_j \in V(G)$ is meant similarly.
  The {\it join} $G \vee F$ of two vertex-disjoint graphs is the graph
  whose  vertex set is $V(G) \cup V(F)$ and two vertices $u$ and $v$ of $G \vee F$ are adjacent
  if and only if either $uv \in E(G)\cup E(F)$, or $u\in V(G)$ and
  $v\in V(F)$.
  The {\it diamond} is a 4-cycle with exactly one chord (or
  equivalently, the graph $K_4-e$ obtained from the complete graph
  $K_4$ by deleting exactly one edge).
  Given a graph $F$, a graph $G$ is said to be {\it $F$-free} if it
  contains no {\it induced} subgraph isomorphic to $F$.


 Next, we define the two main concepts studied in this paper.
 For illustration, see Figure \ref{fig1}.



 \bd For an integer $k\ge 1$, the {\it $k$-line graph} $L_k(G)$ of a graph $G$
 has vertices representing the $k$-cliques of $G$, and two vertices in
 $L_k(G)$ are adjacent if and only if the represented $k$-cliques of
 $G$ intersect in a $(k-1)$-clique. \ed

 For $k=1$  the definition
 yields $L_1(G)=K_n$ for every graph $G$ of
 order $n$. Note  that even the $K_2$-free (edgeless) graph
  with $n$ vertices has the complete graph
 $K_n$ as its 1-line graph.
  The 2-line graph $L_2(G)$ is the line graph of $G$ in the
 usual sense. The 3-line graph is the triangle graph $\cT(G)$.
 
\begin{figure}[H]
\begin{center}
\unitlength 1mm % = 2.85pt
\linethickness{0.4pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi % GNUPLOT compatibility
\begin{picture}(127.61,50)(0,20)
\put(14.75,42.75){\circle{2.24}}
\put(15.5,42.75){\line(1,0){13.25}}
\put(72.25,55.5){\line(0,1){0}}
\put(29.87,42.62){\circle{2.24}}
\put(14.87,28.5){\circle{2.24}}
\put(15.62,28.5){\line(1,0){13.25}}
\put(29.99,28.37){\circle{2.24}}
\put(15,42){\line(1,-1){13.25}}
\put(14.75,42){\line(0,-1){12.25}}
\put(29.75,41.5){\line(0,-1){12.25}}
\put(28.75,42.25){\line(-1,-1){13}}
\put(30.5,42.75){\line(1,0){13.25}}
\put(44.87,42.62){\circle{2.24}}
\put(30.62,28.5){\line(1,0){13.25}}
\put(44.99,28.37){\circle{2.24}}
\put(30,42){\line(1,-1){13.25}}
\put(44.75,41.5){\line(0,-1){12.25}}
\put(43.75,42.25){\line(-1,-1){13}}
\put(2.87,36.62){\circle{2.24}}
%\emline(3.25,35.75)(13.75,29)
\multiput(3.25,35.75)(.05223881,-.03358209){201}{\line(1,0){.05223881}}
%\end
%\emline(13.75,42.75)(3.5,37)
\multiput(13.75,42.75)(-.05994152,-.03362573){171}{\line(-1,0){.05994152}}
%\end
\put(44.62,56.87){\circle{2.24}}
\put(44.75,56){\line(0,-1){12}}
%\emline(43.25,56.75)(15.25,44)
\multiput(43.25,56.75)(-.074074074,-.033730159){378}{\line(-1,0){.074074074}}
%\end
\put(3.37,23.37){\circle{2.24}}
\put(2.75,35.5){\line(0,-1){11.25}}
%\emline(2.75,24.25)(13.75,28.5)
\multiput(2.75,24.25)(.08730159,.03373016){126}{\line(1,0){.08730159}}
%\end
\put(81,70.5){\circle{2.24}}
\put(81.75,70.5){\line(1,0){13.25}}
\put(96.12,70.37){\circle{2.24}}
\put(81.12,56.25){\circle{2.24}}
\put(81.87,56.25){\line(1,0){13.25}}
\put(96.24,56.12){\circle{2.24}}
\put(81.25,69.75){\line(1,-1){13.25}}
\put(81,69.75){\line(0,-1){12.25}}
\put(96,69.25){\line(0,-1){12.25}}
\put(95,70){\line(-1,-1){13}}
\put(96.75,70.5){\line(1,0){13.25}}
\put(111.12,70.37){\circle{2.24}}
\put(96.87,56.25){\line(1,0){13.25}}
\put(111.24,56.12){\circle{2.24}}
\put(96.25,69.75){\line(1,-1){13.25}}
\put(111,69.25){\line(0,-1){12.25}}
\put(110,70){\line(-1,-1){13}}
\put(69.12,64.37){\circle{2.24}}
%\emline(69.5,63.5)(80,56.75)
\multiput(69.5,63.5)(.05223881,-.03358209){201}{\line(1,0){.05223881}}
%\end
%\emline(80,70.5)(69.75,64.75)
\multiput(80,70.5)(-.05994152,-.03362573){171}{\line(-1,0){.05994152}}
%\end
\put(69.62,51.12){\circle{2.24}}
\put(69,63.25){\line(0,-1){11.25}}
\put(112,70.5){\line(1,0){13.25}}
\put(126.37,70.37){\circle{2.24}}
\put(112.12,56.25){\line(1,0){13.25}}
\put(126.49,56.12){\circle{2.24}}
\put(111.5,69.75){\line(1,-1){13.25}}
\put(126.25,69.25){\line(0,-1){12.25}}
\put(125.25,70){\line(-1,-1){13}}
\put(71.5,18){\line(0,1){0}}
\put(80.25,33){\circle{2.24}}
\put(81,33){\line(1,0){13.25}}
\put(95.37,32.87){\circle{2.24}}
\put(80.37,18.75){\circle{2.24}}
\put(81.12,18.75){\line(1,0){13.25}}
\put(95.49,18.62){\circle{2.24}}
\put(80.5,32.25){\line(1,-1){13.25}}
\put(80.25,32.25){\line(0,-1){12.25}}
\put(95.25,31.75){\line(0,-1){12.25}}
\put(94.25,32.5){\line(-1,-1){13}}
\put(110.37,32.87){\circle{2.24}}
\put(110.49,18.62){\circle{2.24}}
\put(110.25,31.75){\line(0,-1){12.25}}
\put(68.37,26.87){\circle{2.24}}
\put(68.87,13.62){\circle{2.24}}
\put(111.25,33){\line(1,0){13.25}}
\put(125.62,32.87){\circle{2.24}}
\put(111.37,18.75){\line(1,0){13.25}}
\put(125.74,18.62){\circle{2.24}}
\put(110.75,32.25){\line(1,-1){13.25}}
\put(125.5,31.75){\line(0,-1){12.25}}
\put(124.5,32.5){\line(-1,-1){13}}
\put(50,33.25){\line(1,-1){9.75}}
\put(57.5,22.5){\line(1,0){3.25}}
\put(60.75,22.5){\line(0,1){3}}
\put(51.5,44.75){\line(1,1){10.75}}
\put(60.75,56.25){\line(1,0){2.75}}
\put(63.25,56.25){\line(0,-1){3.25}}
\end{picture}
%\includegraphics[width=12cm]{Fig1.pdf}
\end{center}
\caption{A graph and its $3$-line graph and $3$-anti-Gallai graph.}\label{fig1}
\end{figure}




 \bd For an integer $k\ge 1$, the {\it $k$-anti-Gallai graph} $\triangle_k(G)$  of a graph
 $G$ has  one vertex for each $k$-clique of $G$, and two
 vertices in $\triangle_k(G)$ are adjacent if and only if the  union of the two $k$-cliques
 represented   by them span a  $(k+1)$-clique in $G$.
  \ed

 Hence, $\triangle_k(G)$ is a
 subgraph of $L_k(G)$. For every graph $G$, its 1-anti-Gallai graph is $G$
 itself, whilst
 2-anti-Gallai  graph means anti-Gallai graph (denoted by $\triangle(G)$)
 in the usual sense.
  If a vertex $c_i$ of $L_k(G)$ or $\triangle_k(G)$
 represents the $k$-clique $C_i$ of $G$, we say that
 $c_i$ is the image of $C_i$ and conversely,
 $C_i$ is the preimage of $c_i$. In notation, if the context is clear,
 the preimage of $c_i$ is denoted either by $C_i$ or by $C(c_i)$.
 A graph $G$ is called $k$-line
 graph or $k$-anti-Gallai graph  if there exists a
 graph $G'$ such that $L_k(G')=G$ or $\triangle_k(G')=G$ holds,
  respectively.

\subsection{Results}


The line graph operator is a classical subject in graph theory.
From the rich literature here we mention only the forbidden
subgraph characterization given by Beineke in 1970 \cite{Bei}.
  The notion of the triangle graph and that of the $k$-line graph were
  introduced several times independently  by different motivations,
  and  studied from different  points of view (see for example
  \cite{Bag, CCM1, CCM2, Cook, Le1,   Pr-book, Pris, Tuza}).
  For earlier results on anti-Gallai and $k$-anti-Gallai graphs we refer the
  reader to the papers \cite{ARV, Dor, Le} and the book \cite{Pr-book}.
  As relates the most recent works, Anand \emph{et al.}\ answered  a question of Le by showing that
  the recognition problem of anti-Gallai graphs is \NP-complete
    \cite{NP-tr-linegr},
  moreover an application of the anti-Gallai graphs to automate the
  discovery of ambiguous words is described in   \cite{linqu}.\\

  In this paper we study three related topics. The first one concerns a
  question of Bagga \cite{Bag} asking for a characterization of
  graphs $G$ for which $G \mathop{\Box} K_n$ is a triangle graph.   As a complete
  solution in a much more general setting, in
  Section~2 we give a necessary and sufficient condition for a
  Cartesian product $G \mathop{\Box} F$ to be a 3-line graph.
  Then, in Section 3, this result is generalized by establishing a
  unified characterization for $G \mathop{\Box} F$ to be a $k$-line graph,
  for  every $k \ge 2$.\\


We also study the algorithmic hardness of recognition
  problems. Due to the forbidden subgraph characterization in
  \cite{Bei}, the 2-line graphs can be recognized in polynomial time.
   In contrast to this, we prove in Section 4 that the analogous problem is
  \NP-complete for the triangle graphs. Then, in Section 5 the same
  hardness is established for $k$-line graphs for each fixed $k \ge 4$.
  Via some lemmas and  a constructive reduction, we obtain that recognizing
  $k$-anti-Gallai graphs is also \NP-complete for each $k\ge 3$. The
  latter result   solves a problem raised by Anand \emph{et
  al.}\ \cite{NP-tr-linegr}, extending their theorem from $k=2$
   to larger values of $k$.\\

In Section 6, graphs with $L_k(G) \cong L(G)$ are identified for
each $k \ge 3$. Finally, in the concluding section we put some
remarks and formalize a problem which remains open.


 \subsection{Some basic facts}



 Here we list some basic statements, which  can be found in \cite{Pr-book}
 or can be proved directly from the definitions.

 \boc[\cite{Pr-book}] \label{3}
 \ Every\/ $k$-line graph is\/ $K_{1,k+1}$-free.
  \eoc

 \bo \label{2} \label{1}
 Every clique\/ $K_n$ of a\/ $k$-line graph\/ $L_k(G)$ either corresponds  to\/
  $n$\/ $k$-cliques of\/ $G$ sharing a fixed\/ $(k-1)$-clique, or
     corresponds to\/ $n$\/ $k$-cliques contained in a common\/ $K_{k+1}.$
     In particular, every clique of order\/ $n$ in a triangle graph\/ $\cT(G)$  corresponds
      to $n$ triangles of\/ $G$ which are either incident with  a fixed edge, or
     contained in a common\/ $K_4$.
  \eo
  \pf
    Let $c_1, \dots, c_n$ be the vertices of an $n$-clique $K_n$ of $L_k(G)$ and
    $C_1, \dots, C_n$ be the corresponding $k$-cliques in $G$.
    Moreover, let $v_1, \dots, v_k \in V(G)$ be the vertices  which induce
      $C_1$.
    Since $c_2$ is adjacent to $c_1$ in $L_k(G)$,
    the $k$-clique $C_2$ has precisely one vertex outside $C_1$.
    We assume without loss of generality that $C_2=\{u, v_2, v_3,
    \dots, v_k\}$.
    Now, suppose that there exists a vertex in $K_n$, say $c_3$,
    such that its preimage   $C_3$ does not contain some
    vertex from the set $C_1 \cap C_2 =\{v_2, v_3, \dots, v_k\}$; say,
    $v_k$ is omitted. In this case, since $c_3$ is adjacent to both
    $c_1$ and $c_2$, the $k$-clique $C_3$ must be induced by $\{u,
    v_1,v_2,  \dots, v_{k-1}\}$. Then, for any further vertex
    $c_i$, the preimage must be of the form $C_i=\{u, v_1, v_2,
    \dots, v_k\}\setminus \{v_{j_i}\}$ for some $2 \le j_i \le k-1$.
    This proves that if not all the intersections $C_i \cap C_j$ are the same, then
    each of the $k$-cliques $C_1, \dots, C_n$ is contained in the
    $(k+1)$-clique $\{u, v_1, v_2,\dots, v_k\}$.\newline \hspace*{0pt} \qed

  \bo \label{k<k'} If\/ $G$ is the\/ $k$-line graph of a\/ $K_{k+1}$-free
  graph, then for every\/ $k'>k$,\/ $G$ is also the\/
  $k'$-line graph of a\/ $K_{k'+1}$-free graph.
  \eo
  \pf Let $G=L_k(H)$ for a $K_{k+1}$-free graph $H$.
   Consider the join $H'=H \vee K_{k'-k}$.
  Since $H$ is $K_{k+1}$-free, $H'$ is $K_{k'+1}$-free and every
    $k'$-clique of $H'$ originates
  from a $k$-clique of $H$ extended by the $k'-k$ new vertices.
  Additionally, two $k'$-cliques of $H'$ intersect in a $K_{k'-1}$ if
  and only if the corresponding $k$-cliques of $H$ meet in a
  $K_{k-1}$. Consequently, $L_{k'}(H')=L_k(H)=G$. \qed

\section{Cartesian product and triangle graphs} \label{prod-tri-gr}

In this section we solve a problem posed in \cite{Bag} by Bagga.


 \thm \label{tr-gr-prod}
 The Cartesian product\/ $G\mathop{\Box} F$ of two nontrivial connected graphs is a triangle graph
 if and only if\/ $F$ is a complete graph and\/ $G$ is the line graph of
 a triangle-free graph (or vice versa).
  \ethm

 Before proving the theorem we verify a lemma.

 \begin{lem}\label{dialemma}
If\/ $G$ contains a diamond as an induced subgraph then\/
  $G\mathop{\Box} K_n$ is not a triangle graph for\/ $n \geq 2$.
\end{lem}
\pf To prove the lemma we apply the following result from
\cite{Bag}.
 \tmz
  \item[$(*)$]   If $H$ is a triangle graph with $K_4 -
e$ as an induced subgraph, then there exists a vertex $x$ in $H$
such that $x$ is adjacent to three vertices of one triangle of $K_4
- e$ and nonadjacent to the fourth vertex.
 \etmz

  Let $G$ be a graph which contains a
 diamond induced by the vertices $u_1,u_2,u_3$ and $u_4$, where
 $(u_1,u_4)$ is the non-adjacent vertex pair.
 Assume for a contradiction
 that there exists a graph H whose triangle graph is $G\mathop{\Box} K_n$
  for some $n \geq 2$. Let $v_1 \in V(K_n)$. Then, $(u_1,v_1), (u_2,v_1),
(u_3,v_1),(u_4,v_1)$ is an induced diamond in $G\mathop{\Box} K_n$. Since
$G\mathop{\Box} K_n$ is a triangle graph, by $(*)$, it must contain a vertex
$( u_5,v_1)$ which is adjacent to all vertices of one of the
triangles in the diamond and not adjacent to the fourth vertex.
 Let $(u_4,v_1)$ be the vertex which is not adjacent to
$( u_5,v_1)$. Let $t_i$ be the triangle in $H$ corresponding to the
vertex $( u_i,v_1)$ in $G\mathop{\Box} K_n$ for $i=1,\dots, 5$. Then $t_1,
t_2, t_3$ and $t_5$ must be the triangles of a $K_4$ and $t_4$ is a
triangle which shares the edge which is common to the triangles
$t_2$ and $t_3$.
 Let $v_2 \in V(K_n)\setminus \{v_1\}$ (it exists, since $n
\geq 2$). Then $( u_1,v_2)$ is adjacent to $(u_i,v_1)$ only for
$i=1$. Therefore, the triangle in $H$ corresponding to the vertex $(
u_1,v_2)$ must share an edge with $t_1$ and not with any other $t_i$
for $i=2,\dots,5$. But, each edge of $t_1$ is shared with at least one
among $t_2$, $t_3$ and $t_5$, which gives a contradiction.
Therefore, $G\mathop{\Box} K_n$ is not a triangle graph. \qed



\bsk

\nin{\bf Proof of Theorem \ref{tr-gr-prod}.}
 If both $G$ and $F$ are non-complete graphs, then
$G \mathop{\Box} F$ contains an induced $K_{1,4} \subset P_3 \mathop{\Box} P_3$ and
hence, by Observation \ref{3}, it is not a triangle graph. So we
can assume that $F=K_n$ for some $n \geq 2$.\\

If $G$ is not a line graph, then by the theorem of Beineke
\cite{Bei}, $G$ contains one of the nine forbidden subgraphs as an
induced subgraph (see Figure \ref{fig2}). If it is $K_{1,3}$,
 then $G \mathop{\Box} K_n$ contains an induced $K_{1,4}$,
 which is forbidden for triangle graphs.
In the case of any of the remaining eight graphs,
 $G$ contains an induced  diamond  and hence, by
Lemma \ref{dialemma}, $G \mathop{\Box} K_n$ cannot be a triangle graph.

\begin{figure}[H]
\begin{center}
\unitlength 1mm % = 2.85pt
\linethickness{0.4pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi % GNUPLOT compatibility
\begin{picture}(87.49,70)(0,0)
\put(12.87,75.62){\circle{2.24}}
\put(13,74.25){\line(0,-1){6.75}}
\put(7.37,59.12){\circle{2.24}}
\put(20.12,59.12){\circle{2.24}}
%\emline(12.5,66.25)(7.25,60.25)
\multiput(12.5,66.25)(-.03365385,-.03846154){156}{\line(0,-1){.03846154}}
%\end
\put(14.25,66.25){\line(1,-1){5.75}}
\put(13.37,66.62){\circle{2.24}}
\put(38.25,72.75){\line(1,-1){5.75}}
\put(37.37,73.12){\circle{2.24}}
\put(44.37,66.12){\circle{2.24}}
\put(36.25,73){\line(-1,-1){6.25}}
\put(30.62,66.37){\circle{2.24}}
\put(43.75,65.5){\line(-1,-1){5.5}}
\put(37.12,60.12){\circle{2.24}}
\put(30.25,65.25){\line(1,-1){5.75}}
\put(31.5,66.25){\line(1,0){11.5}}
\put(53.37,65.87){\circle{2.24}}
%\emline(38.25,73.25)(52.5,66.75)
\multiput(38.25,73.25)(.0738342,-.03367876){193}{\line(1,0){.0738342}}
%\end
%\emline(38,60)(52.75,65)
\multiput(38,60)(.09899329,.03355705){149}{\line(1,0){.09899329}}
%\end
\put(71.25,73.5){\line(1,-1){5.75}}
\put(70.37,73.87){\circle{2.24}}
\put(77.37,66.87){\circle{2.24}}
\put(69.25,73.75){\line(-1,-1){6.25}}
\put(63.62,67.12){\circle{2.24}}
\put(76.75,66.25){\line(-1,-1){5.5}}
\put(70.12,60.87){\circle{2.24}}
\put(63.25,66){\line(1,-1){5.75}}
\put(64.5,67){\line(1,0){11.5}}
%\emline(71.25,74)(85.5,67.5)
\multiput(71.25,74)(.0738342,-.03367876){193}{\line(1,0){.0738342}}
%\end
%\emline(71,60.75)(85.75,65.75)
\multiput(71,60.75)(.09899329,.03355705){149}{\line(1,0){.09899329}}
%\end
\put(38.25,44.25){\line(1,-1){5.75}}
\put(37.37,44.62){\circle{2.24}}
\put(44.37,37.62){\circle{2.24}}
\put(36.25,44.5){\line(-1,-1){6.25}}
\put(30.62,37.87){\circle{2.24}}
\put(43.75,37){\line(-1,-1){5.5}}
\put(37.12,31.62){\circle{2.24}}
\put(30.25,36.75){\line(1,-1){5.75}}
\put(31.5,37.75){\line(1,0){11.5}}
\put(37.62,53.12){\circle{2.24}}
\put(37.5,52){\line(0,-1){6}}
%\emline(37.25,52.25)(30.25,39.25)
\multiput(37.25,52.25)(-.03365385,-.0625){208}{\line(0,-1){.0625}}
%\end
%\emline(37.5,52.25)(44,39)
\multiput(37.5,52.25)(.03367876,-.06865285){193}{\line(0,-1){.06865285}}
%\end
\put(49.37,30.87){\circle{2.24}}
\put(37.75,31.5){\line(1,0){10.5}}
\put(14,47){\line(1,-1){5.75}}
\put(13.12,47.37){\circle{2.24}}
\put(20.12,40.37){\circle{2.24}}
\put(12,47.25){\line(-1,-1){6.25}}
\put(6.37,40.62){\circle{2.24}}
\put(19.5,39.75){\line(-1,-1){5.5}}
\put(12.87,34.37){\circle{2.24}}
\put(6,39.5){\line(1,-1){5.75}}
\put(7.25,40.5){\line(1,0){11.5}}
\put(23.87,47.37){\circle{2.24}}
\put(13.75,47.5){\line(1,0){8.75}}
\put(2.87,33.62){\circle{2.24}}
\put(3.75,33.5){\line(1,0){8.5}}
\put(73.5,47.25){\line(1,-1){5.75}}
\put(72.62,47.62){\circle{2.24}}
\put(79.62,40.62){\circle{2.24}}
\put(71.5,47.5){\line(-1,-1){6.25}}
\put(65.87,40.87){\circle{2.24}}
\put(79,40){\line(-1,-1){5.5}}
\put(72.37,34.62){\circle{2.24}}
\put(65.5,39.75){\line(1,-1){5.75}}
\put(66.75,40.75){\line(1,0){11.5}}
\put(72.37,53.87){\circle{2.24}}
\put(72.37,28.87){\circle{2.24}}
\put(72.5,53){\line(0,-1){4}}
\put(72,53){\line(-3,-5){6.75}}
%\emline(72.75,53)(79.25,42)
\multiput(72.75,53)(.03367876,-.05699482){193}{\line(0,-1){.05699482}}
%\end
\put(65.5,39.75){\line(3,-5){6}}
%\emline(79.5,39.75)(73,29.5)
\multiput(79.5,39.75)(-.03367876,-.05310881){193}{\line(0,-1){.05310881}}
%\end
\put(12,17){\line(1,-1){5.75}}
\put(11.12,17.37){\circle{2.24}}
\put(18.12,10.37){\circle{2.24}}
\put(10,17.25){\line(-1,-1){6.25}}
\put(4.37,10.62){\circle{2.24}}
\put(17.5,9.75){\line(-1,-1){5.5}}
\put(10.87,4.37){\circle{2.24}}
\put(4,9.5){\line(1,-1){5.75}}
\put(5.25,10.5){\line(1,0){11.5}}
\put(21.87,17.37){\circle{2.24}}
\put(11.75,17.5){\line(1,0){8.75}}
\put(21.75,16.5){\line(0,-1){11.25}}
\put(21.87,4.37){\circle{2.24}}
\put(11.5,4.25){\line(1,0){9}}
\put(42.5,17.25){\line(1,-1){5.75}}
\put(41.62,17.62){\circle{2.24}}
\put(48.62,10.62){\circle{2.24}}
\put(40.5,17.5){\line(-1,-1){6.25}}
\put(34.87,10.87){\circle{2.24}}
\put(48,10){\line(-1,-1){5.5}}
\put(41.37,4.62){\circle{2.24}}
\put(34.5,9.75){\line(1,-1){5.75}}
\put(35.75,10.75){\line(1,0){11.5}}
\put(52.37,17.62){\circle{2.24}}
\put(42.25,17.75){\line(1,0){8.75}}
\put(31.37,3.87){\circle{2.24}}
\put(32.25,3.75){\line(1,0){8.5}}
%\emline(34.25,10.5)(31,4.75)
\multiput(34.25,10.5)(-.03350515,-.05927835){97}{\line(0,-1){.05927835}}
%\end
%\emline(52,17)(48.75,11.5)
\multiput(52,17)(-.03350515,-.05670103){97}{\line(0,-1){.05670103}}
%\end
\put(69.75,15.25){\line(1,-1){5.75}}
\put(68.87,15.62){\circle{2.24}}
\put(75.87,8.62){\circle{2.24}}
\put(67.75,15.5){\line(-1,-1){6.25}}
\put(62.12,8.87){\circle{2.24}}
\put(75.25,8){\line(-1,-1){5.5}}
\put(68.62,2.62){\circle{2.24}}
\put(61.75,7.75){\line(1,-1){5.75}}
\put(63,8.75){\line(1,0){11.5}}
\put(79.62,15.62){\circle{2.24}}
\put(69.5,15.75){\line(1,0){8.75}}
\put(79.5,14.75){\line(0,-1){11.25}}
\put(79.62,2.62){\circle{2.24}}
\put(69.25,2.5){\line(1,0){9}}
%\emline(79,15)(75.75,9.5)
\multiput(79,15)(-.03350515,-.05670103){97}{\line(0,-1){.05670103}}
%\end
%\emline(76,8)(79.25,3.75)
\multiput(76,8)(.03350515,-.04381443){97}{\line(0,-1){.04381443}}
%\end
\put(86.37,66.87){\circle{2.24}}
\qbezier(87.25,67.25)(62.75,91.13)(62.25,67.5)
\end{picture}
\end{center}
\caption{Forbidden subgraphs for line graph.}\label{fig2}
\end{figure}

Let $G$ be the line graph of a   graph $H$ which contains a
triangle. Let $T=(u_1, u_2, u_3)$ be a triangle in $H$. If $H \neq
K_3$, there exists a vertex $u_4$ adjacent to some $u_i$ in $T$
(not necessarily to $u_i$ alone). But, then $G = L(H)$ contains a
diamond and hence by Lemma \ref{dialemma},  $G \mathop{\Box} K_n$ is not a
triangle graph. If $H$ is $K_3$ itself, then $H = L(K_{1,3})$
also.

Conversely, let $G$ be the line graph of a triangle-free graph $H$.
Then  $\cT(H \vee \overline{K_n}) = G \mathop{\Box} K_n$, completing the
proof of the theorem. \qed

\bsk

Concerning edgeless graphs, note that  $G \mathop{\Box} K_1  \cong G$, and
hence the characterization problem of graphs $G$ such that $G \mathop{\Box}
K_1$ is a triangle graph is equivalent to characterizing triangle
graphs.

\section{Cartesian product and $k$-line graphs}

As proved in Section \ref{prod-tri-gr}, if both $G$ and $F$ are
nontrivial connected graphs,   $G\mathop{\Box} F$ is a triangle graph if and
only if one of $G$ and $F$ is a line graph  of a $K_3$-free graph
and the other one is a complete graph. We will see  that a direct
analogue of this theorem is not valid for $k$-line graphs in
general. For instance, one can observe that the grid graph $P_n \mathop{\Box}
P_m$ is a $k$-line graph for every  $n,m$ and $k\ge 4$.

Our main result in this section is the following theorem, which
gives a necessary and sufficient condition for a product  $G\mathop{\Box} F$
of non-edgeless graphs to be a $k$-line graph. Recall that $k$-line
graphs were defined for $k=1$, too.


\thm \label{thm-prod-line} For every $k\ge 2$, the product $G \mathop{\Box}
F$ of two non-edgeless connected graphs is a\/ $k$-line graph if
and only if there exist positive integers $k_1$ and\/ $k_2$ such
that $G$ is the\/ $k_1$-line graph of a\/ $K_{k_1+1}$-free
graph,\/ $F$ is the\/ $k_2$-line graph of a\/ $K_{k_2+1}$-free
graph and\/ $ k_1+k_2 \le k$ holds.
 \ethm

If $F$ is   a complete graph then it is the $k_2$-line graph of
 a $K_{k_2+1}$-free graph for every $k_2\ge 1$. (For example,
  $K_n=L_{k_2}(K_{k_2-1} \vee nK_1)$ for all $k_2\ge 1$, where
  the degenerate case $k_2=1$ simply means that
  $K_n=L_1(nK_1)$.)
 Hence, in  this particular case of Theorem \ref{thm-prod-line},
 the existence of an appropriate $k_1\le k-1$ is required.
 By Observation \ref{k<k'}, this is equivalent to the claim that
  $G$ is the $(k-1)$-line graph of
 a $K_{k}$-free graph. Thus, we obtain:

 \bc \label{prod-Kn}
 For every two integers\/ $n\ge 2$ and $k\ge 2$, the product\/ $G\mathop{\Box} K_n$ is a\/ $k$-line
 graph if and only if\/ $G$ is the\/ $(k-1)$-line graph of a\/ $K_k$-free
 graph. \ec

 Theorem \ref{thm-prod-line} will be proved at the end of this
 section. First we need some lemmas.

 \bl \label{diamond}
 \tmz
 \item[$(i)$] If\/ $H$ contains a\/ $K_{k+1}$ subgraph, then for the
 corresponding\/ $(k+1)$-clique\/ $\cC$ of\/ $L_k(H)$, each vertex\/ $c\in
 V(L_k(H))\smin \cC$ is either adjacent to none of the vertices of\/ $\cC$
 or\/ $c$ is adjacent to exactly two vertices of\/ $\cC$.
 \item[$(ii)$] Assume that\/ $k\ge 2$ and no component of the\/
  $k$-line graph\/ $L_k(H)$ is
 isomorphic to\/ $K_{k+1}$.
 Then,\/ $H$ is\/ $K_{k+1}$-free if and only if\/
 $L_k(H)$ is diamond-free.
  \etmz\el

 \pf First, assume that
   $H$ contains a $K_{k+1}$, which is induced by the vertex set  $V=\{v_1, \dots,
 v_{k+1}\}\subseteq V(H)$, and consider the corresponding $(k+1)$-clique $\cC$ in  $L_k(H)$  whose vertices
 $c_1, \dots, c_{k+1}$ represent the $k$-subsets of $V$. If there is a further vertex $c^*$
   adjacent to at least one vertex
  of $\cC$, then in $H$  the $k$-clique $C^*$, which is the preimage
  of   $c^*$, intersects $V$ in exactly $k-1$ vertices. Without loss of generality, we
  assume that for every $c_i$ the preimage is $C_i=V\smin
  \{v_i\}$, moreover that $C^* \cap V=\{v_1, \dots, v_{k-1}\}$.
  Then, $|C^* \cap C_k|=|C^* \cap C_{k+1}|=k-1$, but
  $|C^* \cap C_i|=k-2$ holds for every $1\le i \le k-1$. Therefore,
  $c^*$ is adjacent to exactly two vertices of $\cC$. This
  verifies $(i)$. Concerning $(ii)$, note that if the $(k+1)$-clique
  $\cC$ is not a component of $L_k(H)$ then such a $c^*$ surely
  exists, and if $k\ge 2$,   vertices $c_1,c_k,c_{k+1},c^*$
  induce a diamond in $L_k(H)$.

  For the other direction of $(ii)$, assume that $H$ is $K_{k+1}$-free, and in
  $L_k(H)$  vertices $c_1,c_2,c_3,c_4$ induce a diamond where
  $c_2$ and $c_4$ are nonadjacent.
  By Observation~\ref{2}, the preimages $C_1,C_2,C_3$ of  $c_1,c_2,c_3$ are three
  different  $k$-cliques of $H$ sharing a fixed $(k-1)$-clique.
  Then, $|C_1 \cap C_2 \cap C_3|=k-1$ and
  similarly, $|C_1 \cap C_3 \cap C_4|=k-1$ hold. By the adjacency of $c_1$ and $c_3$, $|C_1 \cap
  C_3|=k-1$ is valid as well. Hence,  the vertex sets $C_1 \cap C_2 \cap
  C_3$ and  $C_1 \cap C_3 \cap C_4$ must be the same,
  contradicting the non-adjacency of $c_2$ and $c_4$. Thus, we conclude
  that for a $K_{k+1}$-free $H$, the $k$-line graph contains no
  induced diamond. \qed

 \bsk

\bl \label{k+1-free}
 If the Cartesian product $G \mathop{\Box} F$ of two
 non-edgeless graphs
 is the $k$-line graph of $H$, then $H$ is
$K_{k+1}$-free. \el
 \pf Suppose for a contradiction that $H$ contains a complete
 subgraph $X$ induced by vertices $x_1, \dots, x_{k+1}$.
 Then, in $L_k(H)= G \mathop{\Box} F$ the vertices $c_1, \dots,c_{k+1}$,
  representing the $k$-cliques
 $C_1, \dots,C_{k+1}\subset X$,  form a complete subgraph.
 Hence, all these vertices $c_1, \dots,c_{k+1}$ must belong
 either to the same copy of $G$ or to  the  same copy of $F$. Assume without
 loss of generality that $c_i=(v_1,u_i)$ for every $1 \le i \le
 k+1$, and let $v_j$ be a neighbor of $v_1$ in $G$. Then, the vertex
 $(v_j,u_1)$ is adjacent to only one  vertex (namely, to $(v_1,u_1)$) from the
 $(k+1)$-clique. This contradicts Lemma \ref{diamond}$(i)$ and
 hence, $H$ is $K_{k+1}$-free. \qed


 \bsk

 \bl \label{4cycle}
 If\/ $G$ is the\/ $k$-line graph of\/ $H$, and\/ $G$ contains an induced cycle\/
 $c_1c_2c_3c_4$, then  the corresponding\/ $k$-cliques
 $C_1,C_2,C_3,C_4$ of\/ $H$ satisfy\/ $C_2\smin C_1=C_3\smin C_4$.
 \el

 \pf As the 1-line graph  $L_1(H)$ is a complete graph, it
 contains no induced four-cycle. Hence, we can assume that $k\ge 2$.
 Let $C_1\smin C_2=\{v_1\}$,  $C_2\smin C_1=\{v_2\}$, $C_1\smin C_4=\{z_1\}$ and
 $C_4\smin C_1=\{z_2\}$.
 We observe that $v_1 \neq z_1$ and $v_2 \neq z_2$,
  as any $v_i=z_i$ would mean the
 adjacency of $c_2$ and $c_4$.
 Now, suppose for a contradiction that $v_2 \notin C_3$.
Since $c_1c_2$ and $c_2c_3$ are edges in $G$ and $v_2 \in C_2$,
but $v_2 \notin C_1$ and $v_2 \in C_3$, it follows that, $C_3 \cap
C_2= C_2\smin \{v_2\}=C_1 \cap C_2$.  This implies $|C_1 \cap
C_3|=k-1$, which  contradicts $c_1c_3\notin E(G)$. Therefore, $v_2
\in C_3$ holds and since $v_2\notin C_4$,  the desired equality
$C_3\smin C_4=\{v_2\}=C_2\smin C_1$ follows. \qed

\bsk

In view of Lemma \ref{4cycle}, we can give a structural
characterization for graphs whose $k$-line graph is the Cartesian
product $G\mathop{\Box} F$ of two non-edgeless graphs. We will use the
following notions.\\


If $L_k(H)=G\mathop{\Box} F$, consider a copy $G_i$ and the $k$-cliques of
$H$ which are represented by the vertices of $G_i$. A vertex
contained in all  these $k$-cliques is called a \emph{universal
vertex}, otherwise it is \emph{non-universal} (with respect to
$G_i$). Formally, let
$$U_i^G(H)=\bigcap \{C(v_j,u_i): v_j \in V(G)\}, ~~ \mbox{and} ~~
X_i^G(H)=\bigcup \{C(v_j,u_i): v_j \in V(G)\}\,\setminus\,
U_i^G(H). $$ Analogously, the sets $U_i^F$ and $X_i^F$ of
universal and non-universal vertices with respect to the copy
$F_i$ are also introduced.

 \bl \label{str-copy}
 Let $G$ and $F$ be two connected graphs and let $L_k(H)=G\mathop{\Box} F$.
 \tmz
 \item[$(i)$] For every two copies $G_i$ and $G_j$ of $G$ the
 non-universal vertices are the same: $X_i^G(H)=X_j^G(H)$.
 \item[$(ii)$] Each copy $G_i$ is the $k$-line graph of the
 subgraph induced by $U_i^G(H) \cup X_i^G(H)$.
 \etmz
 \el
 \pf First assume that  $u_i$ and $u_j$ are adjacent vertices in $F$.
 For every two vertices $v_a$  and $v_b$ of $G$ there is a path
  between $(v_a,u_i)$ and $(v_b,u_i)$ in $G_i$. This path together with the
  corresponding vertices of $G_j$ induces a chain of 4-cycles.
  Hence, the repeated application of Lemma \ref{4cycle} implies that
  $$C(v_a,u_i)\setminus C(v_a,u_j)= C(v_b,u_i)\setminus C(v_b,u_j)
  ~~~ \mbox{and} ~~~
  C(v_a,u_j)\setminus C(v_a,u_i)= C(v_b,u_j)\setminus C(v_b,u_i)
  $$
  for every two vertices $v_a$ and $v_b$ of $G$. As follows,
  there are fixed vertices  $w_{i,j} \in U_i^G(H)$ and $w_{j,i} \in U_j^G(H)$
  such that the preimage of any vertex of copy $G_j$ can be obtained
  from the preimage of the corresponding vertex of copy $G_i$ by
  replacing $w_{i,j}$ with $w_{j,i}$ in the $k$-clique.
  Thus, $U_j^G(H)=(U_i^G(H)\setminus \{w_{i,j}\}) \cup \{w_{j,i}\}$
  and for the non-universal vertices $X_i^G(H)=X_j^G(H)$ holds.
  Since $F$ is connected, the latter equality is valid for
  nonadjacent vertices $u_i,u_j \in V(F)$ as well. This verifies
  $(i)$.

  To prove $(ii)$, observe that $U_i^G(H) \neq U_j^G(H)$ and
   $|U_i^G(H)|= |U_j^G(H)|$ for every
  pair $i,j$. Therefore, neither $U_i^G(H) \setminus
  U_j^G(H)$ nor $U_j^G(H) \setminus U_i^G(H)$ is empty.
  Consequently, every $k$-clique in the subgraph induced by $U_i^G(H) \cup
  X_i^G(H)$ has its image  in copy $G_i$.
  This proves $(ii)$.  \qed

 \bsk

 \nin{\bf Proof of Theorem \ref{thm-prod-line}.}\enskip
   To prove  sufficiency, let $G=L_{k_1}(G')$ and $F=L_{k_2}(F')$
    where $G'$ is
 $K_{k_1+1}$-free, $F'$ is $K_{k_2+1}$-free, and $k_1+k_2 \leq k$.
 Then,  the join $H'=G' \vee F'$ is $K_{k_1+k_2+1}$-free and every
 $(k_1+k_2)$-clique of $H'$ originates from a $k_1$-clique of
 $G '$ and from a $k_2$-clique of $F'$. Thus, the vertices of
 $L_{k_1+k_2}(H')$ correspond to the pairs $(v_i,u_j)$ with $v_i\in V(G) $
 and $u_j\in V(F)$. Moreover two vertices $(v_i,u_j)$ and
  $(v_k,u_\ell)$ in $L_{k_1+k_2}(H')$ are
 adjacent if and only if
 \tmz
 \item either $v_i=v_k$ and the $k_2$-cliques $C(u_j)$ and $C(u_\ell)$
 share a $(k_2-1)$-clique in $F'$, that is $u_ju_\ell \in E(F)$,
 \item  or $u_j=u_\ell$ and the $k_1$-cliques $C(v_i)$ and $C(v_k)$
 share a $(k_1-1)$-clique in $G'$, that is $v_iv_k \in E(G)$.
 \etmz
 Therefore, $L_{k_1+k_2}(H')=G  \mathop{\Box} F$, and by Observation
 \ref{k<k'}, $L_k(H' \vee K_{k-k_1-k_2})=G  \mathop{\Box} F$
 also holds for every $k>k_1+k_2$.

  \bsk

  To prove necessity, suppose that $H=G \mathop{\Box} F$ is the $k$-line
 graph of $H'$. By Lemma \ref{k+1-free}, $H'$ is
 $K_{k+1}$-free.
 Consider the sets $A=U_1^G(H')$ and $B=U_1^F(H')$ of universal vertices
 in copies $G_1$ and $F_1$.

 \msk

\nin  \underline{{\it Claim A.}} $G$ is the $(k-|A|)$-line graph
of a
  $K_{k-|A|+1}$-free graph and
  $F$ is the $(k-|B|)$-line graph of a
  $K_{k-|B|+1}$-free graph.
  \msk

\nin  {\it Proof.} By Lemma \ref{str-copy}$(ii)$,
  $G_1\cong G$ is the $k$-line graph of the
 subgraph $G^* \subset H'$ induced by $A \cup X_1^G(H')$.
    If  the universal vertices of $G^*$ are deleted, we obtain $G'=G^*-A$.
  While constructing $G'$ from $G^*$, every
  $k$-clique is shrunk into a $(k-|A|)$-clique and two cliques
  share exactly $k-|A|-1$ vertices if and only if the corresponding
  vertices of $G$ are adjacent. This proves that $G=L_{k-|A|}(G')$.
  It is clear that $G'$ is $K_{k-|A|+1}$-free. The analogous
  argument for $F$ yields  $F'=F^*-B$ such that $F=L_{k-|B|}(F')$
  and  $F'$ is $K_{k-|B|+1}$-free.

  \msk

\nin  \underline{{\it Claim B.}} $|A|+|B| \ge k$.
  \msk

\nin  {\it Proof.} Assume to the contrary that $|A|+|B| < k$.
Then,
  there exists a vertex $z \in C(v_1,u_1)\smin (A \cup B)$.
  As the graph
  $G_1 \cong G$ is connected and $z$ cannot be contained in all preimages $C(v_\ell,u_1)$,
  there exist adjacent vertices
  $(v_i,u_1)$ and $(v_j,u_1)$ such that $z\in C(v_i,u_1)$ and
  $z\notin C(v_j,u_1)$. This means $C(v_i,u_1)\smin C(v_j,u_1)=\{z\}$.
   Similarly  for
  $F_1$, there exist indices $m$ and $n$ such that
  $C(v_1,u_m)\smin C(v_1,u_n)=\{z\}$ holds. By Lemma
  \ref{4cycle}, for the 4-cycle induced by
  $\{(v_i,u_n),(v_i,u_m),(v_j,u_m),(v_j,u_n)\}$ the following
  equalities hold:
  $$C(v_1,u_m)\smin C(v_1,u_n)=C(v_i,u_m)\smin C(v_i,u_n)=\{z\},$$
  $$C(v_i,u_1)\smin C(v_j,u_1)=C(v_i,u_n)\smin
  C(v_j,u_n)=\{z\}.$$
  They give a contradiction on the question whether $z$ is in
  $C(v_i,u_n)$ or not. This proves $|A|+|B| \ge k$.

  \msk
  Denoting $k_1= k-|A|$ and $k_2= k-|B|$, $k_1+k_2 \le k$ follows
  by Claim B. Then, Claim A proves the  necessity of
  the condition given for $G$ and $F$ in the theorem.
 \qed

 \bsk

 The proof of Theorem \ref{thm-prod-line} also verifies the following
 statement.

 \bc \label{join}
 If\/ $G$ is
$K_{k_1+1}$-free   and \/ $F$ is\/ $K_{k_2+1}$-free, then
$$L_{k_1}(G)\mathop{\Box} L_{k_2}(F)\cong L_{k_1+k_2}(G \vee F).$$
\ec

\section{\NP-completeness of recognizing triangle graphs}
\label{sect-NP-tr}



  As is well-known, the line graphs can be
 recognized in polynomial time due to the forbidden subgraph
 characterization by Beineke \cite{Bei}. Also linear-time algorithms
  were designed for solving this problem \cite{Leh, Rou}.
  Here we prove that triangle graphs (that is, 3-line graphs) are hard
  to recognize.


  \thm \label{triangle-NP}
  The following problems are \NP-complete:
  \tmz
  \item[$(i)$] Recognizing triangle graphs.
   \item[$(ii)$] Deciding whether a given graph is the triangle graph
  of a\/ $K_4$-free graph.
  \etmz
  Moreover, both problems remain \NP-complete on the class of connected graphs.
    \ethm

  Before proving Theorem \ref{triangle-NP}, we verify two
    lemmas which give necessary conditions for graphs to be
  anti-Gallai or triangle graphs of some $K_4$-free graph, respectively.

  \bl Assume that\/ $F$ is a connected non-trivial graph and\/
  $F$ is the anti-Gallai graph of $F'$.
  Then\/ $F'$ is\/ $K_4$-free if and only if every edge of\/ $F$ is contained in exactly
  one triangle, or equivalently
  \tmz \item[$(\star)$]  every maximal clique of\/ $F$ is a
  triangle and any two triangles share at most one vertex. \etmz \el

  \pf If $F'$ contains a $K_4$ subgraph then $F=\triangle(F')$ contains
  an induced $K_6-3K_2$ and $(\star)$ does not hold.
  If $F'$ is $K_4$-free, any three pairwise adjacent vertices in $\triangle(F')$
  correspond to  three edges of $F'$ which form a triangle. Hence no
  edge of $\triangle(F')$ belongs to more than one triangle.
  Additionally, by definition, in an anti-Gallai graph every edge corresponds to
  two preimage-edges of a triangle; hence, every edge of
  $\triangle(F')$ is contained in a $K_3$. Since $F$ is assumed to be
  connected and non-edgeless, it contains no isolated vertices.
  This proves that every maximal clique of $F$ is a $K_3$ and any two
  triangles have at most one vertex in common.
  \qed


  \bl \label{starstar}
  Assume that\/  $G$ is a connected graph which is not isomorphic to\/
  $K_4$, moreover\/  $G= \cT(G')$.
    Then\/ $G'$ is\/ $K_4$-free if and only if
  \tmz \item[$(\star \star)$]  each vertex\/ of $G$ is
  contained in at most three maximal cliques and these cliques are
  pairwise edge-disjoint. \etmz \el
  \pf In this proof, the vertex of $G$ whose preimage is a triangle
  $abc$ in $G'$ will be denoted by $t_{abc}$.

  First suppose that $G'$ contains a $K_4$ induced by the vertices $x,y,z,u$.
 Clearly, the four triangles of the $K_4$ correspond to a 4-clique
 in $\cT(G')$. By our condition
   $\cT(G')$ is not a 4-clique, hence there exists a triangle in $G'$, containing
 exactly two vertices from $x,y,z,u$. Say, this
 triangle is $xyw$. In $\cT(G')$, the vertex originated from $xyz$ is
 contained in both cliques induced by the vertex sets
 $\{t_{xyz},t_{xyu},t_{yzu},t_{xzu}\}$ and
 $\{t_{xyz},t_{xyu},t_{xyw}\}$, respectively. Maybe the second
 clique is not maximal, but since there is no edge between
 $t_{yzu}$ and $t_{xyw}$, there are two different maximal cliques
 with the common edge $t_{xyz}t_{xyu}$. This shows that $(\star \star)$ does
 not hold.

 For the converse, suppose that $G'$ is $K_4$-free. Then by
 Observation \ref{1}, each clique of $\cT(G')$ corresponds
 to triangles  sharing a fixed edge in $G'$.
 Thus,  a vertex $t_{xyz} \in V(\cT(G))$ can be
 contained only in  those  maximal cliques which correspond
 to the three edges of its preimage-triangle (one or two of these cliques might be
 missing) and any two of these maximal cliques have  $t_{xyz}$ as the  only common vertex, hence
 $(\star \star)$ holds.
 \qed

 \bsk



 While proving that the recognition problem of triangle graphs is
 \NP-complete, we will use the following notion.
     The {\it triangle-restriction\/} of a graph is obtained if
     the edges not contained in any triangles and the
     possibly arising isolated vertices are deleted.
      Every graph has a triangle-restriction,
     and the application of this operator
     changes neither the anti-Gallai graph (if it is
     connected)\footnote{If some edges of a graph $F'$ are not contained
     in any triangles, their images in the anti-Gallai graph are
     isolated vertices. The deletion of these edges from $F'$
     results in the deletion of all isolated vertices from the
     anti-Gallai
     graph.},
     nor the triangle graph.
     A graph is called {\it triangle-restricted\/}
       if  each edge and each vertex of it
     belongs to a triangle.
      The {\it clique graph\/} $\cK(G)$ of a graph G is the
       intersection graph of the set
   of all \emph{maximal} cliques of G.\footnote{That is, the vertices of $\cK(G)$
   correspond to the maximal cliques of $G$ and two vertices of $\cK(G)$
   are adjacent if the corresponding cliques share at least one
   vertex.}

  \bsk


  \nin{\bf Proof of Theorem \ref{triangle-NP}.}\enskip
  The decision problems are clearly in \NP. The  \NP-completeness of $(ii)$
    will be
  reduced from the following theorem recently proved by Anand et
  al.\  \cite{NP-tr-linegr}:
   Deciding whether a connected graph $F$ is the anti-Gallai graph of
  some  $K_4$-free graph is an \NP-complete problem.

  Consider an instance $F$  to decide whether it is the
 anti-Gallai graph of a $K_4$-free graph. In the first step, we check
 the necessary condition  $(\star)$; if it does not hold, $F$ is not
 the anti-Gallai graph of any $K_4$-free graphs.
  From now on, suppose that $(\star)$ holds for $F$. Then every maximal clique of
  $F$ is a triangle and the
  clique graph $G=\cK(F)$ is exactly the triangle-intersection graph of $F$.
  If $F$ is connected then so is  $G$, and $G\cong K_4$
  holds if and only if $F$ is the union of four triangles sharing
  exactly one vertex. Hence, from now on we assume that $G \not\cong K_4$.
  In addition, if $F$ fulfills  property $(\star)$, then  its triangle-intersection graph
   $G$ fulfills property $(\star  \star)$.

  Next, we prove that $F$ is the anti-Gallai graph of a $K_4$-free
  triangle-restricted graph $H$ if and only if $G$ is the triangle
  graph of $H$.

  Assume that $F=\triangle(F')$. By $(\star)$,
    $F'$ is $K_4$-free, hence its triangles are
  in one-to-one correspondence with the triangles of
    $F$ and by $(\star)$ this yields a one-to-one correspondence with the
    vertices of $G$. Moreover two triangles in $F'$ share an edge if
    and only if the corresponding triangles share a vertex in $F$;
    and if and only if the corresponding vertices in the
    clique graph $G$ are adjacent. Therefore,
    $G=\cT(F')$.

  To prove the other direction, assume that $G=\cT(G')$. Since $G$
  satisfies $(\star  \star)$, $G'$ must be $K_4$-free. We can choose $G'$ to be
  triangle-restricted.  Now, for every vertex $t\in V(G)$,
  if $t$ is contained in only two maximal cliques, then in addition
  the 1-element vertex set $\{t\}$ will also be considered as
  a `maximal clique' of $G$. Similarly, if $t$ is contained in only
  one clique of $G$, then $\{t\}$ is also taken as a `maximal clique' with
  multiplicity 2. Then the edges of $G'$ are in one-to-one
  correspondence with the maximal cliques of $G$. These maximal
  cliques are in one-to-one correspondence with the vertices of $F$,
  where the one-element cliques of $G$ represent vertices contained
   in only one triangle
  of  $F$. Also, two edges of $G'$ belong to a common triangle if
  and only if the corresponding maximal cliques have a common vertex
  (which represents the triangle); that is, if and only if the two
  vertices of $F$, represented by the cliques, are adjacent. This
  proves $F=\triangle(G')$.


  Checking $(\star)$ and constructing $G$ from $F$ takes
  polynomial time. So, the recognition problem of the anti-Gallai
  graphs can be  reduced to that of the triangle
  graphs in polynomial time. Hence,
  the recognition problem  of triangle graphs is \NP-complete and
   this remains valid on the class of connected graphs
    satisfying $(\star\star)$.
\qed



\section{Recognizing generalized line graphs and anti-Gallai graphs}

In this section we turn to the recognition problems of general
$k$-line graphs and $k$-anti-Gallai graphs.
  In sharp contrast to the linear-time recognizability of $k$-line
  graphs for $k\le 2$, by Theorem \ref{triangle-NP} the analogous problem is
    \NP-complete for $k=3$.
    Also, anti-Gallai graphs are hard to recognize
    as  proved by Anand et al.\ via a reduction from 3-SAT \cite{NP-tr-linegr}.
  Now, we complete these results by proving that
  the recognition problems of $k$-line graphs and $k$-anti-Gallai graphs are
  \NP-complete for each $k\ge 3$.

\thm The following problems are \NP-complete for every fixed\/
  $k\ge 3$:
 \tmz
 \item[$(i)$] Recognizing\/ $k$-line graphs.
  \item[$(ii)$] Deciding whether a given graph is the\/  $k$-line graph of a\/ $K_{k+1}$-free
  graph.
  \etmz
  Moreover both problems remain  \NP-complete on the class of connected graphs. \ethm

 \pf Clearly,  problems $(i)$ and $(ii)$ are in \NP.
  Moreover, by Theorem \ref{triangle-NP},   both problems are \NP-complete
   for $k=3$, already on the class of connected graphs.
   Therefore, we can proceed by induction on   $k$.

   For the inductive step, assume that
     $k\ge 4$ and that
     $(ii)$ is
   \NP-complete for $k-1$ on the class of connected graphs.
   Let $G$ be a connected graph  and construct the
   Cartesian product $H=G\mathop{\Box} K_2$, which is also connected.
   Due to Corollary \ref{prod-Kn},  $G$ is a $(k-1)$-line graph of
   a $K_{k}$-free graph if and only if $H$ is a $k$-line graph of   a $K_{k+1}$-free graph.
   Therefore, $(ii)$ is \NP-complete for every $k\ge 3$.
   On the other hand, by Lemma \ref{k+1-free} a graph of the form
   $G\mathop{\Box} K_2$ is a $k$-line
   graph if and only if it is a $k$-line graph of a $K_{k+1}$-free
   graph. Hence, the above reduction also proves the \NP-completeness of $(i)$ for every
   $k\ge 3$. \qed

   \bsk

   Before proving the same hardness for the recognition problem of
   $k$-anti-Gallai graphs, we state a lemma. Note that part $(i)$
    gives the same condition (namely diamond-freeness) for
   $\triangle_k(G)$ as Lemma \ref{diamond} does for $L_{k+1}(G)$
    to ensure that $G$ is $K_{k+2}$-free.

   \bl \label{k+2-free-AG}
   For every\/ $k\ge 2$,  every graph\/ $G$ and its\/ $k$-anti-Gallai
   graph\/ $\triangle_k(G)$ satisfy the following relations:
   \tmz
   \item[$(i)$] $G$ is\/ $K_{k+2}$-free if and only if\/  $\triangle_k(G)$
   is diamond-free.
   \item[$(ii)$] $G$ is\/ $K_{k+2}$-free if and only if    each maximal
   clique of\/  $\triangle_k(G)$   is either an isolated vertex or a\/
   $(k+1)$-clique.
   Moreover any  two maximal cliques intersect in at most one vertex.
   \etmz
   \el
   \pf First, assume that $G$ contains a $(k+2)$-clique induced by
   the vertex set $V=\{v_1, \dots,v_{k+2}\}$. Consider the following
   $k$-cliques:
   $$C_1=V\setminus \{v_1,v_2\}, \quad
   C_2=V\setminus \{v_2,v_3\}, \quad
   C_3=V\setminus \{v_1,v_3\}, \quad
   C_4=V\setminus \{v_1,v_4\}.$$
   Any two of these $k$-cliques are in a common $(k+1)$-clique
   except the pair $(C_2,C_4)$. Therefore, in the $k$-anti-Gallai graph
    the corresponding vertices $c_1,c_2,c_3$ and $c_4$ induce a diamond.
    In addition, the two maximal cliques containing
    $c_1c_2c_3$ and $c_1c_3c_4$, respectively, must be different and
    intersect in more than one vertex.

    To prove the other direction of $(i)$ and $(ii)$, assume that $G$ is
    $K_{k+2}$-free. First, consider an edge $c_ic_j \in
    E(\triangle_k(G))$. The union $C_i \cup C_j$ of the represented $k$-cliques
    induces a $K_{k+1}$ subgraph in $G$, whose $k$-clique subgraphs
    are represented by vertices forming a $K_{k+1}$ subgraph in
    $\triangle_k(G)$. Hence, every edge of $\triangle_k(G)$ belongs to a
    $(k+1)$-clique.
    Now, suppose that  $c_ic_jc_\ell$ is a triangle in $\triangle_k(G)$.
    The union $C_i \cup C_j$ of the preimage cliques induces a $K_{k+1}$ in
    $G$.
    Also  $C_i \cup C_j\cup C_\ell$ induces a complete subgraph as
     every two of its vertices are contained in a common
    clique.
    Since $G$ is  $K_{k+2}$-free, $C_i \cup C_j\cup C_\ell$ is a
    $(k+1)$-clique as well, and $C_\ell \subset C_i \cup C_j$ must
    hold.
    This implies that in the $k$-anti-Gallai graph, every two adjacent
    vertices $c_i$, $c_j$ together with all their common neighbors form a
    $(k+1)$-clique.
    As follows  concerning $(i)$, $\triangle_k(G)$ contains no induced
    diamond. Furthermore, each edge belongs to exactly one maximal clique of
    $\triangle_k(G)$ and this must be a $(k+1)$-clique.
     These  complete the proof of $(i)$ and $(ii)$. \qed

  \bsk


   \thm The following problems are \NP-complete for every fixed\/
  $k\ge 3$:
 \tmz
   \item[$(i)$] Recognizing\/ $k$-anti-Gallai graphs.
   \item[$(ii)$] Recognizing\/ $k$-anti-Gallai graphs on the class of
   connected and diamond-free graphs.
   \item[$(iii)$] Deciding whether a given connected graph is a\/  $k$-anti-Gallai
   graph of a\/ $K_{k+2}$-free graph.
    \etmz
   \ethm

   \pf The membership in  \NP~is obvious for each of $(i)$--$(iii)$.
   As diamond-freeness can be checked in polynomial time,
   statements $(ii)$ and
   $(iii)$ imply each other by Lemma \ref{k+2-free-AG}$(i)$.
   It is also clear that $(ii)$ implies
   $(i)$. Then, it is enough to prove $(iii)$.
   For $k=2$, problem $(iii)$  was proved to be
   \NP-complete in \cite{NP-tr-linegr}.

   We proceed by induction on $k$.
   Consider a generic connected  instance $G$ and an integer $k\ge
   3$.

    For each fixed $k$, the condition given in Lemma \ref{k+2-free-AG}$(ii)$
    can be checked in polynomial time.
    If it does not hold, $G$  cannot be a $k$-anti-Gallai graph of
    any $K_{k+2}$-free graph.
    From now on we suppose that every maximal clique of $G$ is of order
    $k+1$ and any two maximal cliques have at most one vertex in
    common. For such a $G$ we construct the following
    graph $G_e$ and prove that $G$ is  a $k$-anti-Gallai graph
      if and only if $G_e$ is a $(k+1)$-anti-Gallai graph.

    \msk

\nin    \underline{{\it Construction of $G_e$.}} Take two disjoint
copies $G^1$ and
    $G^2$ of  $G$ with vertex sets $V(G^j)=\{c_i^j: c_i \in V(G)\}$
    ($j=1,2$), moreover one vertex $b_s$ for each $(k+1)$-clique
    $B_s$ of $G$. Besides the edges of $G^1$ and $G^2$ take all
    edges of the form $b_sc_i^j$ for which $c_i \in B_s$ and $j=1,2$ hold.

    \msk

    As $G$ consists of $(k+1)$-cliques such that any two of them
    intersect in at most one vertex, $G_e$ consists of $(k+2)$-cliques such that any two of them
    intersect in at most one vertex.

    \msk
\nin    \underline{{\it Claim C.}} If $G=\triangle_k(G')$ then
$G_e=\triangle_{k+1}(G'\vee
    2K_1)$.
    \msk

\nin    {\it Proof.} Let $\cB$ denote the set of $k$-cliques of
$G'$.
     Corresponding to the relation $G=\triangle_k(G')$,
     we have a  bijection $\phi: \cB \mapsto V(G)$ such that every
    $k$-clique of $G'$ is mapped to the vertex representing it in
    $\triangle_k(G')$.

    Partition the set $\cA$ of $(k+1)$-cliques of the join $G_e'=G'\vee
    \{z_1,z_2\}$ into three subsets. An $A \in \cA$ is said to be of
    Type 1 or 2 or 3 if it contains $z_1$, or $z_2$, or
    none of them, respectively. (Since $z_1$ and $z_2$ are nonadjacent, no clique
    contains both of them.)

    Now, define a bijection $\vp: \cA \mapsto V(G_e)$ as follows.
    For every $A\in \cA$,
       $$ \vp(A)= \left\{
 \begin{array}{cl}
  (\phi(A\setminus \{z_1\})^{1} & \mbox{if $A$ is of Type 1,}\\
  (\phi(A\setminus \{z_2\})^{2} & \mbox{if $A$ is of Type 2,}\\
   b_\ell & \mbox{if $A$ is of Type 3, and $A$ is the  $(k+1)$-clique $B_\ell$ of $G'$.}
    \end{array}
 \right.
 $$
  To prove Claim C, we show that two $(k+1)$-cliques $A_1$
  and $A_2$ of $G_e'$ are contained in a common $K_{k+2}$ if
  and only if $\vp(A_1)$ and $\vp(A_2)$ are adjacent in $G_e$.
      \tmz
    \item Type-1 cliques are mapped onto $V(G^1)$.
    In addition, two  cliques $A_1$, $A_2$ of Type 1 are contained in a
    common $(k+2)$-clique in $G_e'$ if and only if $A_1 \setminus
    \{z_1\}$ and $A_2\setminus \{z_1\}$ are in a common
    $(k+1)$-clique in $G'$; or equivalently, if and only if
    $(\phi(A_1\setminus \{z_1\})^{1}$ and $(\phi(A_2\setminus
    \{z_1\})^{1}$ are adjacent in $G^1$.
    Similarly, Type-2 cliques are mapped onto $V(G^2)$ and the
    adjacencies in $G^2$ correspond to the adjacencies  required in
    $\triangle_{k+1}(G_e')$.
    \item If  $A_1$ is of Type 1  and $A_2$ is of Type 3,
     their images  are  adjacent in $\triangle_{k+1}(G_e')$
     if and only if $A_1 \setminus \{z_1\} \subset A_2$;
    that is, if the $(k+1)$-clique $A_2$ contains the $k$-clique
    $A_1 \setminus \{z_1\}$ in $G'$.
    This corresponds to the adjacency defined in Construction of $G_e$.
    The analogous property holds for  cliques of Type 2 and Type 3.
    \item Since $z_1$ and $z_2$ are nonadjacent, no two cliques,
    one of Type 1 and the other of Type 2, belong to a common $K_{k+2}$ in $G_e'$.
     Correspondingly, by the construction, there is no edge between $V(G^1)$ and $V(G^2)$ in $G_e$.
     Finally, as $G'$ is $K_{k+2}$-free,  no two  $(k+1)$-cliques of
     Type 3 are in a common $(k+2)$-clique in $G_e'$. This
      corresponds to the fact that
      $V(G_e) \setminus (V(G^1) \cup V(G^2))$ is an independent
      vertex set.
    \etmz
    These observations prove that $G_e=\triangle_{k+1}(G_e')$.

     \bsk

     Concerning the following claim, let us recall that Construction of
     $G_e$ is applied for a  ($K_{k+2}$, diamond)-free graph $G$, and
      yields a ($K_{k+3}$, diamond)-free $G_e$.

    \msk
\nin    \underline{{\it Claim D.}} If  $G_e =\triangle_{k+1}(F')$
then
    there exist two vertices $z_1,z_2 \in V(F')$ such that $G=
    \triangle_k(F'-\{z_1,z_2\})$.
        \msk

\nin    {\it Proof.}
    By Lemma \ref{k+2-free-AG}, $F'$ must be $K_{k+3}$-free.
    Consider a $(k+2)$-clique  $D_\ell$ of $G_e$.
    This  contains exactly one vertex from $V(G_e) \setminus (V(G^1) \cup
    V(G^2))$, say $b_\ell$, and assume
    that the other vertices of $D_\ell$ are from $V(G^1)$.
    The preimages of the vertices of $D_\ell$
    are  exactly the  $(k+1)$-clique subgraphs of a $(k+2)$-clique $A_\ell$
    of $F'$. There is a unique vertex $u_\ell$, called complementing vertex of
    $D_\ell$,
    such that $u_\ell\in A_\ell$. Moreover it is not
    contained in the preimage $C(b_\ell)$ but is contained in the
    preimage of each further vertex of $D_\ell$.
    For this vertex,
    $A_\ell\setminus C(b_\ell)=\{u_l\}$ holds, and
    $C(c_i^1)\smin C(b_\ell)= \{u_l\}$ is valid for every $c_i^1\in
    D_\ell$.


    Assume for a contradiction that there exist two different complementing
    vertices for the $(k+2)$-cliques meeting $V(G^1)$.
    By the connectivity of $G^1$, there exist
    two $(k+2)$-cliques, say  $D_1$ and $D_2$, intersecting in a vertex $c_i^1$
    with complementing vertices  $u_1\neq u_2$.
    Then, consider the vertices $b_1\in D_1$, $b_2\in D_2$,
     the induced 4-cycle $c_i^1b_1c_i^2b_2$ in $G_e$ and the
    preimage $(k+1)$-cliques $C_i^1$, $B_1$, $C_i^2$, $B_2$.
    Since $c_i^1b_1, c_i^1b_2 \in E(G_e)$,
    there exist vertices $x$ and $y$ in $F'$ such that
    $$B_1=C_i^1\smin \{u_1\} \cup \{x\}, \quad B_2=C_i^1\smin \{u_2\} \cup
    \{y\}.$$
        By our assumption, $u_1\neq u_2$. Moreover, $x\neq y$ must be valid,
    since $x=y$ would imply for $B_1 \cup B_2= C_i^1\cup \{x\}$ to be a
    $(k+2)$-clique, contradicting $b_1b_2 \notin E(G_e)$.
    Further,
     if any two vertices coincide from
     the remaining pairs of $u_1,u_2,x,y$,
     it would contradict the above definition of
    $x$ and $y$. Hence, $u_1,u_2,x,y$ are four different
    vertices and the intersection $M=C_i^1\cap B_1\cap B_2=B_1\cap B_2$
    is a $(k-1)$-clique.
    Observe that  the vertices in $M\cup \{u_1,u_2,x,y\}$ are
    pairwise adjacent as contained together in at least one of the $(k+2)$-cliques
     $C_i^1 \cup B_1$ and $C_i^1 \cup B_2$,  the only exception is the
     pair $x,y$. They are surely nonadjacent, as otherwise  $M\cup
     \{u_1,u_2,x,y\}$ would be  a forbidden $(k+3)$-clique in
     $F'$.


     Next, consider the $k$-element intersections $C_i^2\cap
    B_1$ and $C_i^2\cap B_2$. Both of them must contain the entire $M$ and one further
    vertex from $\{x,u_2\}$ and $\{y,u_1\}$, respectively. But all
    the four possible choices are forbidden. The choice $(u_2,u_1)$
    would mean $C_i^1=C_i^2$; any of the  choices  $(x,u_1)$ or $(u_2,y)$ would imply that
    $C_i^1 \cup C_i^2$ is a $(k+2)$-clique, contradicting
    $c_i^1c_i^2 \notin E(G_e)$; and finally, the choice $(x,y)$
    contradicts the non-adjacency of $x$ and $y$.
     By this contradiction we conclude that all $(k+2)$-cliques intersecting $G^1$
     have the same complementing vertex,
    say $z_1$, and the similar result for $G^2$ with the common
    complementing vertex $z_2$ also follows.
    Deleting these vertices from   $F'$, we obtain the graph $F''$
    for which $ \triangle_k(F'')=G$ holds.


    Via Claims C and D, we have proved that $G $ is the $k$-anti-Gallai graph of some
    $K_{k+2}$-free graph if and only if $G_e$ is the $(k+1)$-anti-Gallai graph
    of some $K_{k+3}$-free graph.
    We conclude that  if problem $(iii)$ is \NP-complete for an integer $k\ge
    2$, the same hardness follows for $k+1$. Moreover, the reduction takes time polynomial in
    terms of $|V(G)|$ and $k$.
     This proves $(iii)$  from which $(i)$ and $(ii)$ directly follow. \qed



\section{Graphs with isomorphic line graph and $k$-line graph}



 \bl \label{kn}If\/ $K_n$ is a subgraph of\/ $L_k(G)$ for\/ $n\ge
k+2$, then the\/ $k$-cliques in\/ $G$ corresponding to these\/ $n$
vertices in\/ $L_k(G)$ share\/ $k-1$ vertices.

 \el

\pf By Observation \ref{2}, the vertices of $K_n$ either correspond
to $n$ $k$-cliques of $G$ contained in a common $K_{k+1}$, or
correspond to $n$ $k$-cliques sharing a fixed $(k-1)$-clique. The
former case is impossible  if $n \ge k+2$. Hence, the statement
follows.
 \qed

\thm Let\/ $G$ be a connected graph. Then, for any\/ $k \ge 3$,\/
$L_k(G) \cong L(G)$ holds if and only if\/ $G=K_{k+2}$. \ethm

\pf We begin with the remark that $K_{k+2}$ indeed satisfies
$L_k(K_{k+2}) \cong L(K_{k+2})$. Isomorphism can be established by
the vertex-complementarity of edges (2-cliques) and $k$-cliques.
Two edges of $K_{k+2}$ share a vertex (and hence are adjacent in
$L(K_{k+2})$) if and only if their complementing $k$-tuples
($k$-cliques) share exactly $k-1$ vertices (and hence are adjacent
in $L_k(K_{k+2})$).

The rest of the proof is devoted to the ``only if'' part. Let $G$
be a connected graph such that $L_k(G) \cong L(G)$. Let $t =
\omega(L_k(G))=\omega(L(G))$. If $t \geq k+2$, then by Lemma
\ref{kn}, the $k$-cliques in $G$ corresponding to the $t$ vertices
in $L_k(G)$ that induce a $t$-clique, share $k-1$ vertices.

 Therefore, $\Delta(G) \ge k-2+t$
    and hence
$\omega(L(G)) \ge k-2+t >t$ for $k \ge 3$,
  which contradicts $\omega(L(G)) = t$.

 Therefore, $t \leq k+1$, which means
$\omega(L(G)) \leq k+1$.
 Thus
$\Delta(G) \leq k+1$, from which $\omega(G) \leq k+2$ clearly
follows.
 Moreover,
since, $L_k(G)$ is not the null graph, $\omega(G) \geq k$ also
holds. Hence, we have $k \leq \omega(G) \leq k+2$. In the rest of
the proof we consider the three possible values of $\omega$.

\bsk

\nin{\it Case 1.} $\omega(G) = k$

\ssk

We saw earlier that a 4-clique in $L_k(G)$ would require in $G$
 either a $(k+1)$-clique or a $(k-1)$-clique with four
 external neighbors.
Hence in the current situation with $\Delta(G) \leq k+1$
 and $\omega(G) = k$
 we must have $\omega(L_k(G)) \leq 3$, which also means
  $\omega(L(G)) \leq 3$ and therefore $G$ has
 $\Delta(G) \le 3$.
 Then $\omega(G) \leq 4$, that is $k = 3$ or 4.
 We show that these cases cannot occur.

 For $k=3$, the condition $\Delta(G) \leq 3$ implies
 that $\Delta(L_3(G)) \leq 1 < 2 \leq \Delta(L(G))$ holds,
 hence $L_3(G) \not\cong L(G)$.
 For $k=4$, $\Delta(G) \leq 3$ yields $G \cong K_4$,
 thus $L_4(K_4) = K_1 \not\cong L(K_4)$.
 Consequently, $L_k(G) \not\cong L(G)$ if $\omega(G) = k$.

\bsk

\nin{{\it Case 2.} $\omega(G) = k+1$

\msk

\nin{\it Subcase A: \ $G$ contains only one\/ $K_{k+1}$}

\ssk

Since $\Delta(G) \leq k+1$,
 $G$ contains no $(k-1)$-clique with $k+1$ common external
 neighbors. Hence,
 $L_k(G)$ also has only one
 $K_{k+1}$. Therefore, $L(G)$ also contains only one $K_{k+1}$ and
hence $G$ has only one vertex of degree $k+1$. It means that only
one vertex of $K_{k+1}$ in $G$ has a neighbor outside the
$K_{k+1}$, so that $L_k(G) = L_k(K_{k+1}) = K_{k+1}$ (for $G$ is
connected, $L(G)$ is connected and hence $L_k(G)$ is connected).
But, $L(G) \neq K_{k+1}$. Therefore, $G$ must contain more than
one $K_{k+1}$.

\msk

\nin{\it Subcase B: \ $G$ contains two\/ $K_{k+1}$ subgraphs which
share\/ $l>0$ vertices
 }

\ssk

In this case, $\Delta(G) \ge 2k-l+1$. By $\Delta(G) \le k+1$ we
see that $l=k$, therefore $K_{k+2}-e \subseteq G$. Since $L_k(G)$
is connected and $k$ vertices in $K_{k+2}-e$ already attained the
maximum possible degree $k+1$, $L_k(G) = L_k(K_{k+2}-e)$ must
hold.
 But then the number of vertices in $L_k(G)$ is strictly less
than the number of vertices in $L(G)$, which is a contradiction.

\msk

\nin{\it Subcase C: \ $G$ contains a $K_{k+1}$ which does not
share vertices with any other $K_{k+1}$}

\ssk

Either this reduces to subcase A or, by connectivity, $k-1$
vertices of this $K_{k+1}$ belong to a $k$-clique outside this
$K_{k+1}$. In that case, these $k-1$ vertices cannot have any
further neighbors (since they attained the maximum degree $k+1$)
and there are only two more vertices in the $K_{k+1}$ under
consideration. If $k>3$ then, since $L_k(G)$ is connected, there
are no further $k$-cliques in $G$ and hence $L_k(G)$ is $K_{k+1}$
together with a vertex having exactly two neighbors in $K_{k+1}$,
  which is obviously not isomorphic to $L(G)$. If $k=3$, using
the same arguments, we can see that $L_k(G)$ is a $K_4$ with one
or two further vertices having exactly two neighbors in $K_4$. In
either case, $L_k(G) \neq L(G)$.

\bsk

\nin{\it Case 3.} $\omega(G)=k+2$

\msk

In this case $\Delta(G) \leq k+1$ together with connectivity
implies $G=K_{k+2}$, and this is exactly what had to be proven.
 \qed



\section{Concluding remarks}


  Concerning the algorithmic complexity of recognizing $k$-line graphs,
  the problem is trivial for $k=1$, solvable in linear-time for
  $k=2$, and as we have proved, it becomes \NP-complete for each $k \ge
  3$.
 It is worth noting that there is a further jump
   between the
  behavior of 2- and 3-line graphs, which likely is in connection
  with the jump occurring in time complexity.
   Namely, this further difference is in the uniqueness of
   preimages. As a matter of fact, each connected line graph
   different from $K_3$ has a unique preimage if we disregard
   isolated vertices. In other words, viewing the situation from the
   side of preimages, the line graphs of two non-isomorphic graphs
   containing no isolated vertices and no $K_3$-components surely
   are non-isomorphic.
   The similar statement is not true for triangle graphs, even if we
   suppose that every edge of the preimage is contained in a
   triangle. For example, there are seven essentially different
   graphs whose triangle graph is the 8-cycle (see Figure \ref{fig3}).
   Additionally,
   the number of non-isomorphic pre-images of an $n$-cycle goes to infinity
   as  $n \rightarrow \infty$ \cite{ABT}.

\begin{figure}[H]\label{fig3}
\begin{center}
%TeXCAD Picture [Fig3.pic]. Options:
%\grade{\on}
%\emlines{\off}
%\epic{\off}
%\beziermacro{\on}
%\reduce{\on}
%\snapping{\off}
%\quality{8.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{4.0000}
\unitlength 1mm % = 2.85pt
\linethickness{0.4pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi % GNUPLOT compatibility
\begin{picture}(141.49,60)(0,15)
\put(7.37,62.12){\circle{2.24}}
\put(20.12,62.37){\circle{2.24}}
\put(19.62,49.87){\circle{2.24}}
\put(7.37,49.87){\circle{2.24}}
\put(8,62.25){\line(1,0){11}}
\put(8,49.75){\line(1,0){10.75}}
\put(20,61.5){\line(0,-1){11}}
\put(7.25,61.25){\line(0,-1){10.75}}
\put(2.62,67.37){\circle{2.24}}
\put(23.62,68.12){\circle{2.24}}
\put(3.87,44.87){\circle{2.24}}
%\emline(3.25,67)(6.75,63.5)
\multiput(3.25,67)(.03365385,-.03365385){104}{\line(0,-1){.03365385}}
%\end
%\emline(3.5,67)(19.25,63)
\multiput(3.5,67)(.13235294,-.03361345){119}{\line(1,0){.13235294}}
%\end
%\emline(3,66.75)(6.5,51)
\multiput(3,66.75)(.03365385,-.15144231){104}{\line(0,-1){.15144231}}
%\end
%\emline(7.5,63.25)(22.75,67.5)
\multiput(7.5,63.25)(.12103175,.03373016){126}{\line(1,0){.12103175}}
%\end
%\emline(23,67.5)(20,63.75)
\multiput(23,67.5)(-.0337079,-.0421348){89}{\line(0,-1){.0421348}}
%\end
%\emline(23.5,67.25)(20.25,50.5)
\multiput(23.5,67.25)(-.03350515,-.17268041){97}{\line(0,-1){.17268041}}
%\end
%\emline(4.75,44.75)(19.75,49)
\multiput(4.75,44.75)(.11904762,.03373016){126}{\line(1,0){.11904762}}
%\end
%\emline(4,45.75)(7,49.25)
\multiput(4,45.75)(.0337079,.0393258){89}{\line(0,1){.0393258}}
%\end
%\emline(3.25,46)(6.25,61.75)
\multiput(3.25,46)(.0337079,.1769663){89}{\line(0,1){.1769663}}
%\end
\put(24.37,43.62){\circle{2.24}}
%\emline(20.5,61.5)(24,44.5)
\multiput(20.5,61.5)(.03365385,-.16346154){104}{\line(0,-1){.16346154}}
%\end
%\emline(19.75,49.25)(23.5,45)
\multiput(19.75,49.25)(.03348214,-.03794643){112}{\line(0,-1){.03794643}}
%\end
%\emline(8,49.25)(23.25,43.75)
\multiput(8,49.25)(.0929878,-.03353659){164}{\line(1,0){.0929878}}
%\end
\put(55.12,42.62){\circle{2.24}}
\put(42.87,42.62){\circle{2.24}}
\put(43.5,42.5){\line(1,0){10.75}}
\put(38.87,53.62){\circle{2.24}}
\put(57.87,53.87){\circle{2.24}}
\put(48.12,63.87){\circle{2.24}}
%\emline(39,52.75)(42.25,43.5)
\multiput(39,52.75)(.03350515,-.09536082){97}{\line(0,-1){.09536082}}
%\end
%\emline(57.5,53)(55.25,43.75)
\multiput(57.5,53)(-.0335821,-.1380597){67}{\line(0,-1){.1380597}}
%\end
\put(47,63.25){\line(-1,-1){8.25}}
\put(49,63.5){\line(1,-1){8}}
%\emline(57,55.5)(58,54.5)
\multiput(57,55.5)(.033333,-.033333){30}{\line(0,-1){.033333}}
%\end
\put(30.87,59.37){\circle{2.24}}
\put(65.62,60.37){\circle{2.24}}
\put(47.87,72.37){\circle{2.24}}
%\emline(31.5,58.75)(38,54.5)
\multiput(31.5,58.75)(.0515873,-.03373016){126}{\line(1,0){.0515873}}
%\end
%\emline(31.75,59.75)(46.75,64)
\multiput(31.75,59.75)(.11904762,.03373016){126}{\line(1,0){.11904762}}
%\end
%\emline(30.75,58.5)(41.75,43)
\multiput(30.75,58.5)(.033639144,-.047400612){327}{\line(0,-1){.047400612}}
%\end
%\emline(48.75,64)(64.75,60.5)
\multiput(48.75,64)(.15384615,-.03365385){104}{\line(1,0){.15384615}}
%\end
%\emline(58.25,54.5)(64.5,60)
\multiput(58.25,54.5)(.03810976,.03353659){164}{\line(1,0){.03810976}}
%\end
%\emline(65.25,59.75)(55.75,43.5)
\multiput(65.25,59.75)(-.033687943,-.057624113){282}{\line(0,-1){.057624113}}
%\end
\put(47.75,71.5){\line(0,-1){6.75}}
%\emline(39.5,53)(54.25,43.75)
\multiput(39.5,53)(.053636364,-.033636364){275}{\line(1,0){.053636364}}
%\end
%\emline(56.75,53.5)(43,43.5)
\multiput(56.75,53.5)(-.046296296,-.033670034){297}{\line(-1,0){.046296296}}
%\end
%\emline(47.5,71.75)(38.25,54.75)
\multiput(47.5,71.75)(-.033636364,-.061818182){275}{\line(0,-1){.061818182}}
%\end
\put(38.25,54.75){\line(-1,0){.25}}
%\emline(48.25,71.5)(58,55)
\multiput(48.25,71.5)(.033737024,-.057093426){289}{\line(0,-1){.057093426}}
%\end
\put(92.37,42.37){\circle{2.24}}
\put(80.12,42.37){\circle{2.24}}
\put(80.75,42.25){\line(1,0){10.75}}
\put(76.12,53.37){\circle{2.24}}
\put(95.12,53.62){\circle{2.24}}
\put(85.37,63.62){\circle{2.24}}
%\emline(76.25,52.5)(79.5,43.25)
\multiput(76.25,52.5)(.03350515,-.09536082){97}{\line(0,-1){.09536082}}
%\end
%\emline(94.75,52.75)(92.5,43.5)
\multiput(94.75,52.75)(-.0335821,-.1380597){67}{\line(0,-1){.1380597}}
%\end
\put(84.25,63){\line(-1,-1){8.25}}
\put(86.25,63.25){\line(1,-1){8}}
%\emline(94.25,55.25)(95.25,54.25)
\multiput(94.25,55.25)(.033333,-.033333){30}{\line(0,-1){.033333}}
%\end
\put(102.87,60.12){\circle{2.24}}
\put(85.12,72.12){\circle{2.24}}
%\emline(86,63.75)(102,60.25)
\multiput(86,63.75)(.15384615,-.03365385){104}{\line(1,0){.15384615}}
%\end
%\emline(95.5,54.25)(101.75,59.75)
\multiput(95.5,54.25)(.03810976,.03353659){164}{\line(1,0){.03810976}}
%\end
%\emline(102.5,59.5)(93,43.25)
\multiput(102.5,59.5)(-.033687943,-.057624113){282}{\line(0,-1){.057624113}}
%\end
\put(85,71.25){\line(0,-1){6.75}}
%\emline(84.75,71.5)(75.5,54.5)
\multiput(84.75,71.5)(-.033636364,-.061818182){275}{\line(0,-1){.061818182}}
%\end
%\emline(85.5,71.25)(95.25,54.75)
\multiput(85.5,71.25)(.033737024,-.057093426){289}{\line(0,-1){.057093426}}
%\end
\put(86.12,48.37){\circle{2.24}}
%\emline(76.5,53.25)(84.75,48.75)
\multiput(76.5,53.25)(.06156716,-.03358209){134}{\line(1,0){.06156716}}
%\end
%\emline(87,49)(94,53.25)
\multiput(87,49)(.05555556,.03373016){126}{\line(1,0){.05555556}}
%\end
\put(80.5,43){\line(1,1){5}}
\put(86.5,48){\line(1,-1){4.75}}
\put(129.87,49.12){\circle{2.24}}
\put(117.62,49.12){\circle{2.24}}
\put(118.25,49){\line(1,0){10.75}}
\put(113.62,60.12){\circle{2.24}}
\put(132.62,60.37){\circle{2.24}}
\put(122.87,70.37){\circle{2.24}}
%\emline(113.75,59.25)(117,50)
\multiput(113.75,59.25)(.03350515,-.09536082){97}{\line(0,-1){.09536082}}
%\end
%\emline(132.25,59.5)(130,50.25)
\multiput(132.25,59.5)(-.0335821,-.1380597){67}{\line(0,-1){.1380597}}
%\end
\put(121.75,69.75){\line(-1,-1){8.25}}
\put(123.75,70){\line(1,-1){8}}
\put(140.37,66.87){\circle{2.24}}
%\emline(123.5,70.5)(139.5,67)
\multiput(123.5,70.5)(.15384615,-.03365385){104}{\line(1,0){.15384615}}
%\end
%\emline(133,61)(139.25,66.5)
\multiput(133,61)(.03810976,.03353659){164}{\line(1,0){.03810976}}
%\end
%\emline(140,66.25)(130.5,50)
\multiput(140,66.25)(-.033687943,-.057624113){282}{\line(0,-1){.057624113}}
%\end
\put(114.5,60.25){\line(1,0){17}}
%\emline(122.5,69.5)(117.5,50)
\multiput(122.5,69.5)(-.03355705,-.13087248){149}{\line(0,-1){.13087248}}
%\end
\put(109.87,41.87){\circle{2.24}}
%\emline(113,59)(109.75,43)
\multiput(113,59)(-.03350515,-.16494845){97}{\line(0,-1){.16494845}}
%\end
\put(116.75,48.5){\line(-1,-1){6.5}}
\put(110.25,42){\line(0,1){0}}
\put(123.87,41.12){\circle{2.24}}
\put(110.75,41.75){\line(1,0){12.25}}
%\emline(118,48.5)(123.25,42.25)
\multiput(118,48.5)(.03365385,-.0400641){156}{\line(0,-1){.0400641}}
%\end
%\emline(124.25,42)(129,48.75)
\multiput(124.25,42)(.03368794,.04787234){141}{\line(0,1){.04787234}}
%\end
%\emline(131.75,59.75)(123.5,42.25)
\multiput(131.75,59.75)(-.033673469,-.071428571){245}{\line(0,-1){.071428571}}
%\end
\put(36.37,37.87){\circle{2.24}}
\put(36.87,14.62){\circle{2.24}}
\put(48.12,26.37){\circle{2.24}}
\put(24.37,26.62){\circle{2.24}}
\put(27.87,35.37){\circle{2.24}}
\put(45.62,34.62){\circle{2.24}}
\put(27.37,18.62){\circle{2.24}}
\put(45.12,19.12){\circle{2.24}}
\put(36.12,26.37){\circle{2.24}}
%\emline(28.75,35.75)(35.25,37.75)
\multiput(28.75,35.75)(.1083333,.0333333){60}{\line(1,0){.1083333}}
%\end
%\emline(37.25,37.75)(44.25,35.25)
\multiput(37.25,37.75)(.0933333,-.0333333){75}{\line(1,0){.0933333}}
%\end
\put(46,34.25){\line(1,-4){1.75}}
%\emline(47.75,25.5)(45.25,19.75)
\multiput(47.75,25.5)(-.0333333,-.0766667){75}{\line(0,-1){.0766667}}
%\end
%\emline(37.75,15)(44.25,18.75)
\multiput(37.75,15)(.05803571,.03348214){112}{\line(1,0){.05803571}}
%\end
%\emline(28,18.25)(35.5,14.75)
\multiput(28,18.25)(.07211538,-.03365385){104}{\line(1,0){.07211538}}
%\end
%\emline(24.5,25.5)(26.75,19.75)
\multiput(24.5,25.5)(.0335821,-.0858209){67}{\line(0,-1){.0858209}}
%\end
%\emline(27.25,34.75)(24.25,27.5)
\multiput(27.25,34.75)(-.0337079,-.0814607){89}{\line(0,-1){.0814607}}
%\end
\put(36,37){\line(0,-1){9.25}}
\put(36,25.25){\line(0,-1){9.75}}
\put(37.25,26.25){\line(1,0){9.75}}
\put(25.25,26.5){\line(1,0){9.75}}
%\emline(28.5,35)(35.25,27.5)
\multiput(28.5,35)(.03358209,-.03731343){201}{\line(0,-1){.03731343}}
%\end
%\emline(36.75,27.25)(44.75,33.75)
\multiput(36.75,27.25)(.04145078,.03367876){193}{\line(1,0){.04145078}}
%\end
%\emline(36.75,25.75)(44,19.75)
\multiput(36.75,25.75)(.04073034,-.03370787){178}{\line(1,0){.04073034}}
%\end
%\emline(35.25,26)(27.75,19)
\multiput(35.25,26)(-.03605769,-.03365385){208}{\line(-1,0){.03605769}}
%\end
\put(75.37,36.87){\circle{2.24}}
\put(75.87,13.62){\circle{2.24}}
\put(87.12,25.37){\circle{2.24}}
\put(63.37,25.62){\circle{2.24}}
\put(66.87,34.37){\circle{2.24}}
\put(84.62,33.62){\circle{2.24}}
\put(66.37,17.62){\circle{2.24}}
\put(84.12,18.12){\circle{2.24}}
%\emline(67.75,34.75)(74.25,36.75)
\multiput(67.75,34.75)(.1083333,.0333333){60}{\line(1,0){.1083333}}
%\end
%\emline(76.25,36.75)(83.25,34.25)
\multiput(76.25,36.75)(.0933333,-.0333333){75}{\line(1,0){.0933333}}
%\end
\put(85,33.25){\line(1,-4){1.75}}
%\emline(86.75,24.5)(84.25,18.75)
\multiput(86.75,24.5)(-.0333333,-.0766667){75}{\line(0,-1){.0766667}}
%\end
%\emline(76.75,14)(83.25,17.75)
\multiput(76.75,14)(.05803571,.03348214){112}{\line(1,0){.05803571}}
%\end
%\emline(67,17.25)(74.5,13.75)
\multiput(67,17.25)(.07211538,-.03365385){104}{\line(1,0){.07211538}}
%\end
%\emline(63.5,24.5)(65.75,18.75)
\multiput(63.5,24.5)(.0335821,-.0858209){67}{\line(0,-1){.0858209}}
%\end
%\emline(66.25,33.75)(63.25,26.5)
\multiput(66.25,33.75)(-.0337079,-.0814607){89}{\line(0,-1){.0814607}}
%\end
\put(66.75,33.5){\line(0,-1){15.75}}
\put(66.75,17.75){\line(1,0){16.5}}
\put(67.25,33.25){\line(1,0){16.5}}
\put(83.75,33.25){\line(0,-1){14.25}}
\put(74.5,36){\line(-1,-1){10.5}}
%\emline(64,25.5)(75.25,14.75)
\multiput(64,25.5)(.035266458,-.03369906){319}{\line(1,0){.035266458}}
%\end
\put(75.25,14.75){\line(1,1){10.75}}
%\emline(86,25.5)(75.5,36.25)
\multiput(86,25.5)(-.033653846,.034455128){312}{\line(0,1){.034455128}}
%\end
\put(115.12,35.87){\circle{2.24}}
\put(126.87,24.37){\circle{2.24}}
\put(103.12,24.62){\circle{2.24}}
\put(106.62,33.37){\circle{2.24}}
\put(124.37,32.62){\circle{2.24}}
\put(106.12,16.62){\circle{2.24}}
\put(123.87,17.12){\circle{2.24}}
%\emline(107.5,33.75)(114,35.75)
\multiput(107.5,33.75)(.1083333,.0333333){60}{\line(1,0){.1083333}}
%\end
%\emline(116,35.75)(123,33.25)
\multiput(116,35.75)(.0933333,-.0333333){75}{\line(1,0){.0933333}}
%\end
\put(124.75,32.25){\line(1,-4){1.75}}
%\emline(126.5,23.5)(124,17.75)
\multiput(126.5,23.5)(-.0333333,-.0766667){75}{\line(0,-1){.0766667}}
%\end
%\emline(103.25,23.5)(105.5,17.75)
\multiput(103.25,23.5)(.0335821,-.0858209){67}{\line(0,-1){.0858209}}
%\end
%\emline(106,32.75)(103,25.5)
\multiput(106,32.75)(-.0337079,-.0814607){89}{\line(0,-1){.0814607}}
%\end
\put(106.5,32.5){\line(0,-1){15.75}}
\put(106.5,16.75){\line(1,0){16.5}}
\put(107,32.25){\line(1,0){16.5}}
\put(123.5,32.25){\line(0,-1){14.25}}
\put(114.25,35){\line(-1,-1){10.5}}
%\emline(125.75,24.5)(115.25,35.25)
\multiput(125.75,24.5)(-.033653846,.034455128){312}{\line(0,1){.034455128}}
%\end
%\emline(125.75,24.75)(106.5,16.75)
\multiput(125.75,24.75)(-.08088235,-.03361345){238}{\line(-1,0){.08088235}}
%\end
\put(112.87,23.37){\circle{2.24}}
%\emline(111.5,23)(106.25,17.25)
\multiput(111.5,23)(-.03365385,-.03685897){156}{\line(0,-1){.03685897}}
%\end
\put(103.75,24.25){\line(1,0){8.25}}
%\emline(113.75,23.5)(122.75,18)
\multiput(113.75,23.5)(.05487805,-.03353659){164}{\line(1,0){.05487805}}
%\end
\end{picture}
\end{center}
\caption{The seven triangle restricted graphs whose triangle graph is $C_8$.}\label{fig3}
\end{figure}

Finally, we make some remarks on an open problem closely related to
the results of this paper.

For an integer $k\ge 1$, the vertices of the {\it $k$-Gallai graph}
$\Gamma_k(G)$  represent the $k$-cliques of $G$, moreover its two
vertices  are adjacent if and only if the corresponding $k$-cliques
of $G$ share a $(k-1)$-clique but they are not contained in a common
 $(k+1)$-clique.
  By this definition, the 1-Gallai graph
  $\Gamma_1(G)$ is exactly the complement $\overline{G}$ of $G$, whilst
   2-Gallai graph means Gallai graph in the usual sense, as introduced by Gallai in \cite{Gal}.
 Obviously, $\Gamma_k(G) \subseteq L_k(G)$ holds. Moreover  $\triangle_k(G)$ and $\Gamma_k(G)$ together
 determine an edge   partition of the $k$-line graph.
 Our theorems together with the earlier results from \cite{Bei} and
 \cite{NP-tr-linegr}  determine the time complexity of
 recognition problems of the $k$-line graphs and the $k$-anti-Gallai graphs
 for each fixed $k\ge 1$. Since $G=\Gamma_1(\overline{G})$, every graph is a
 1-Gallai graph. But for each $k\ge 2$ this recognition problem
 remains open.

  \bpm Determine the time
 complexity of the recognition problem of $k$-Gallai graphs for
 $k\ge 2$.
  \epm


\SquashBibFurther
\begin{thebibliography}{99}

  \bibitem{linqu}
 P. Anand, H. Escuadro, R. Gera, and C. Martell, Triangular line
graphs and word sense disambiguation,
 Discrete Appl. Math. 159   (2011), 1160--1165.

 \bibitem{NP-tr-linegr}
 P. Anand, H. Escuadro, R. Gera, S. G. Hartke and D. Stolee,
 On the hardness of recognizing triangular line graphs,
 Discrete Math.
 312  (2012), 2627--2638.

 \bibitem{ABT}
  S.  Aparna Lakshmanan, Cs.  Bujt\'as and Zs.  Tuza, Small edge sets meeting all
 triangles of a graph,
   Graphs Combin. 28   (2012), 381--392.

%   \bibitem{ABT2}
%  S.  Aparna Lakshmanan, Cs.  Bujt\'as and Zs.  Tuza,
%  Induced cycles in triangle graphs,
%  manuscript (2012).

  \bibitem{ARV}
  S. Aparna Lakshmanan, S. B. Rao, and A. Vijayakumar, Gallai and anti-Gallai graphs
  of a graph, Math. Bohem. 132 (2007), 43--54.


\bibitem{Bag}
J. Bagga,
 Old and new generalizations of line graphs,
  Int. J. Math. Math. Sci. 29 (2004), 1509--1521.

\bibitem{Bei}
L. W. Beineke, Characterizations of derived graphs, J. Combin. Theory
9 (1970), 129--135.

 \bibitem{CCM1}
M. Conforti, D. G. Corneil and A. R. Mahjoub, $K_i$-covers I:
complexity and polytopes, Discrete Math. 58 (1986), 121--142.

 \bibitem{CCM2}
   M. Conforti, D. G. Corneil and A. R. Mahjoub, $K_i$-covers II:
$K_i$-perfect graphs, J.~Graph Theory 11 (1987), 569--587.

 \bibitem{Cook}
   C. R. Cook, Two characterizations of interchange graphs of
complete $m$-partite graphs, Discrete Math. 8 (1974), 305--311.

  \bibitem{Dor}
 D. Dorrough, Convergence of sequences of iterated triangular line
 graphs,
 Discrete Math. 161 (1996), 79--86.

\bibitem{Gal}
T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci.
Hungar. 18 (1967), 25--66.


 \bibitem{Le1}
 V. B. Le, Perfect $k$-line graphs and $k$-total graphs, J. Graph Theory 17 (1993), 65--73.

\bibitem{Le}
V. B. Le,
 Gallai graphs and anti-Gallai graphs,
  Discrete Math. 159 (1996), 179--189.

\bibitem{Leh}
  P. Lehot,
  An optimal algorithm to detect a line graph and output its root graph,
  J.~ACM 21 (1974), 569--575.

\bibitem{Pr-book} E. Prisner, Graph Dynamics, Longman, 1995.

\bibitem{Pris}
E. Prisner,
 Intersection multigraphs of uniform hypergraphs,
  Graphs Combin. 14 (1998), 363--375.

\bibitem{Rou}
N. D. Roussopoulos,
  A max $m,n$ algorithm for detecting the graph
  $H$ from its line graph $G$,
   Inform. Process. Lett. 2 (1973), 108--112.

   \bibitem{Tuza}
   Zs. Tuza, Some open problems on colorings and coverings of graphs (Abstract),
  Graphentheorie-Tagung Oberwolfach (1990).




\end{thebibliography}




\end{document}


**********************

 a
 more precise notation for the preimages are $L_k^{-1}(c_i)$ and
 $\Delta_k^{-1}(c_i)$.
