Generalized Line Graphs: Cartesian Products and Complexity of Recognition

[摘要] 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

[学科分类] 离散数学和组合数学

[关键词] Triangle graph;k-line graph;anti-Gallai graph;cartesian product graph