Independence equivalence classes of paths

DOI10.1016/J.DISC.2022.113143MaRDI QIDQ2092372zbMATH OpenOpenAlexFDO

Authors Boon Leong Ng

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.01592

zbMATH Keywords

independence equivalenceindependence polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The independence equivalence class of a graph $G$ is the set of graphs that have the same independence polynomial as $G$. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron (2019) showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.

Recommendations

• Independence equivalence classes of paths and cycles
• Independence equivalence classes of cycles
• A way to construct independence equivalent graphs
• On the unimodality of independence polynomial of certain classes of graphs
• Graphs with unique maximum independent sets

Cites work

• A way to construct independence equivalent graphs
• Clique polynomials and independent set polynomials of graphs
• Independence equivalence classes of cycles
• Independence equivalence classes of paths and cycles
• Independence roots and independence fractals of certain graphs
• Indistinguishable trees and graphs
• Weakly distinguishing graph polynomials on addable properties

Cited in

(5)

• The congruence axiom and path independence
• Independent sets which meet all longest paths
• Path-independent consideration
• Independence equivalence classes of cycles
• Independence equivalence classes of paths and cycles

This page was built for publication: Independence equivalence classes of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2092372)