Independence equivalence classes of paths and cycles

zbMATH Open1429.05152arXiv1810.05317MaRDI QIDQ5206913FDOQ5206913

Authors: I. Beaton, Ben Cameron, Jason I. Brown 

Publication date: 19 December 2019

Abstract: The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size. Two graphs are said to be extit{independence equivalent} if they have equivalent independence polynomials. We extend previous work by showing that independence equivalence class of every odd path has size 1, while the class can contain arbitrarily many graphs for even paths. We also prove that the independence equivalence class of every even cycle consists of two graphs when $nge2$ except the independence equivalence class of $C_6$ which consists of three graphs. The odd case remains open, although, using irreducibility results from algebra, we were able show that for a prime $pgeq5$ and $nge1$ the independence equivalence class of $C_{p^n}$ consists of only two graphs.

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

Recommendations

• Independence equivalence classes of cycles
• Independence equivalence classes of paths
• A way to construct independence equivalent graphs
• Independence roots and independence fractals of certain graphs
• On circulants uniquely characterized by their independence polynomials.

zbMATH Keywords

independence polynomial

Mathematics Subject Classification ID

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

Cites Work

• Practical graph isomorphism. II.
• Roots of independence polynomials of well covered graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the location of roots of independence polynomials
• On the roots of independence polynomials of almost all very well-covered graphs
• The roots of the independence polynomial of a clawfree graph
• On the location of roots of graph polynomials
• Independence roots and independence fractals of certain graphs
• On the coefficients of the independence polynomial of graphs
• On chromatic equivalence of graphs
• A way to construct independence equivalent graphs
• On circulants uniquely characterized by their independence polynomials.
• Some results on the independence polynomial of unicyclic graphs
• Title not available (Why is that?)
• On weakly distinguishing graph polynomials
• Title not available (Why is that?)

Cited In (5)

• Graphs whose independence fractals are line segments
• The congruence classes of paths and cycles
• Independence equivalence classes of cycles
• The congruence axiom and path independence
• Independence equivalence classes of paths

Uses Software

• nauty
• Traces

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

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