TOPICS
Search

Path Complement Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
PathComplementGraph

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.

ngraph name
1singleton graph K_1
2empty graph K^__2
3P_2+K_1
4path graph P_4
5house graph
6tetragonal antiwedge graph

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.

The simplex graphs of the path complement graph P^__n is the Fibonacci cube graph F_n (Alikhani and Ghanbari 2014).

See also

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

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.

Cite this as:

Weisstein, Eric W. "Path Complement Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PathComplementGraph.html

Subject classifications