{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T13:17:21Z","timestamp":1649078241646},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"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\\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 NP-complete for each $k\\ge 3$.<\/jats:p>","DOI":"10.37236\/3983","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:26:14Z","timestamp":1578651974000},"source":"Crossref","is-referenced-by-count":2,"title":["Generalized Line Graphs: Cartesian Products and Complexity of Recognition"],"prefix":"10.37236","volume":"22","author":[{"given":"Aparna","family":"Lakshmanan S.","sequence":"first","affiliation":[]},{"given":"Csilla","family":"Bujt\u00e1s","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2015,9,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i3p33\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i3p33\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:13:08Z","timestamp":1579237988000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v22i3p33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2015,7,1]]}},"URL":"https:\/\/doi.org\/10.37236\/3983","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,11]]}}}