engleski

On path graphs of incidence graphs

For a given graph G and a positive integer k the P_k-path graph P_k(G) has for vertices the set of paths of length k in G. Two vertices are connected in P_k(G) when the intersection of the corresponding paths forms a path of length k-1 in G, and their union forms either a cycle or a path of length k+1. Path graphs were proposed as a generalization of line graphs. In this article we investigate some properties of path graphs of bipartite graphs, especially path graphs of incidence graphs of configurations.

path graph; bipartite graph; perfect graph; incidence graph

nije evidentirano