\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{kk$,\/ $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{kk_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)$.