Note on the subgraph component polynomial

zbMATH Open1298.05168arXiv1311.6856MaRDI QIDQ406698FDOQ406698

Authors: Yunhua Liao, Yaoping Hou 

Publication date: 9 September 2014

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

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.

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

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

Recommendations

• scientific article; zbMATH DE number 6890347
• 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

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)

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• The bivariate Ising polynomial of a graph
• An extension of the bivariate chromatic polynomial
• Graph polynomials and their applications. I: The Tutte polynomial
• Recurrence relations and splitting formulas for the domination polynomial
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterization of graphs using domination polynomials
• Many-to-many disjoint paths in faulty hypercubes
• Path partitions of hypercubes
• A survey of the theory of hypercube graphs
• An introduction to matching polynomials
• An introduction to chromatic 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
• Distinguishing graphs by their left and right homomorphism profiles
• The enumeration of vertex induced subgraphs with respect to the number of components
• The covered components polynomial: a new representation of the edge elimination polynomial
• Graphs determined by polynomial invariants
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• On graphs determined by their Tutte polynomials
• A new expression for matching polynomials
• Polynomial graph invariants from homomorphism numbers

Cited In (7)

• Using Edge-Induced and Vertex-Induced Subhypergraph Polynomials
• Inclusion-exclusion by ordering-free cancellation
• Title not available (Why is that?)
• An abstraction of Whitney's broken circuit theorem
• The enumeration of vertex induced subgraphs with respect to the number of components
• Title not available (Why is that?)
• A graph polynomial arising from community structure (extended abstract)

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)