Note on the subgraph component polynomial

MaRDI QIDQ406698zbMATHFDO

Authors Yunhua Liao, Yaoping Hou

Publication date 9 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Enumeration in graph theory (05C30)

Abstract: Tittmann, Averbouch and Makowsky [P. Tittmann, I. Averbouch, J.A. Makowsky, The enumeration of vertex induced subgraphs with respect to the number of components, European Journal of Combinatorics, 32 (2011) 954-974], introduced the subgraph component polynomial $Q(G;x,y)$ which counts the number of connected components in vertex induced subgraphs. It contains much of the underlying graph's structural information, e.g. the order, the size, the independence number. We show that there are several other graph invariants, like the connectivity, the number of cycles of length four in a regular bipartite graph, are determined by the subgraph component polynomial. Using the obtained results, we find several well-known families of graphs are determined by $Q(G;x,y)$: paths, cycles, tadpole graphs, complete bipartite graphs, friendship graphs, book graphs and hypercubes. Moreover, we study the distinguish power and find some simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the Tutte polynomial and the character polynomial. These are answers to three questions concerning the subgraph component polynomial proposed by Tittmann et al.

Recommendations

• Publication:4568191
• Graph characterising polynomials
• Graphs determined by polynomial invariants
• A Graph Polynomial Approach to Primitivity
• The enumeration of vertex induced subgraphs with respect to the number of components

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A new expression for matching polynomials
• A survey of the theory of hypercube graphs
• An extension of the bivariate chromatic polynomial
• An introduction to chromatic polynomials
• An introduction to matching polynomials
• Characterization of graphs using domination polynomials
• Distinguishing graphs by their left and right homomorphism profiles
• Graph polynomials and their applications. I: The Tutte polynomial
• Graphs determined by polynomial invariants
• Many-to-many disjoint paths in faulty hypercubes
• On graphs determined by their Tutte polynomials
• On the matching polynomial of subdivision graphs
• On the maximal connected component of hypercube with faulty vertices
• On the two largest \(Q\)-eigenvalues of graphs
• Path partitions of hypercubes
• Polynomial graph invariants from homomorphism numbers
• Recurrence relations and splitting formulas for the domination polynomial
• The bivariate Ising polynomial of a graph
• The covered components polynomial: a new representation of the edge elimination polynomial
• The enumeration of vertex induced subgraphs with respect to the number of components
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings

Cited in

(7)

• Inclusion-exclusion by ordering-free cancellation
• An abstraction of Whitney's broken circuit theorem
• The enumeration of vertex induced subgraphs with respect to the number of components
• Using Edge-Induced and Vertex-Induced Subhypergraph Polynomials
• scientific article; zbMATH DE number 6890347 (Why is no real title available?)
• A graph polynomial arising from community structure (extended abstract)
• scientific article; zbMATH DE number 3893227 (Why is no real title available?)

This page was built for publication: Note on the subgraph component polynomial

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