Path Complement Graph


The n-path complement graph P^__n is the graph complement of the path graph P_n. The first few are illustrated above.

Since P_4 is self-complementary, P^__4 is isomorphic to P_4. Special cases are summarized in the table below.

P^__n has vertex count n and edge count

 m(P^__n)=(n-1; 2)=1/2(n-2)(n-1),

where (n; k) is the binomial coefficient.

P^__n is connected for n>=4 and Hamiltonian for n>=5.

See also

Cycle Complement Graph, Graph Complement, House Graph, Path Graph, Tetragonal Antiwedge, Wheel Complement Graph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Path Complement Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications