Note on the subgraph component polynomial

MaRDI QIDQ406698zbMATH OpenFDO

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, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p27

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

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

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.

Review text

Summary: \textit{P. Tittmann} et al. [Eur. J. Comb. 32, No. 7, 954--974 (2011; Zbl 1229.05124)] introduced the subgraph component polynomial \(Q(G;x,y)\) of a graph \(G\), which counts the number of connected components in vertex induced subgraphs. This polynomial encodes a large amount of combinatorial information about the underlying graph, such as the order, the size, and the independence number. We show that several other graph invariants, such as the connectivity and the number of cycles of length four in a regular bipartite graph are also determined by the subgraph component polynomial. Then, we prove that several well-known families of graphs are determined by the polynomial \(Q(G;x,y)\). Moreover, we study the distinguishing power and find simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial. These are partial answers to three open problems proposed by Tittmann et al. [loc. cit.].

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

Cites work

• 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
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• 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
• Using Edge-Induced and Vertex-Induced Subhypergraph Polynomials
• scientific article; zbMATH DE number 6890347 (Why is no real title available?)
• An abstraction of Whitney's broken circuit theorem
• scientific article; zbMATH DE number 3893227 (Why is no real title available?)
• A graph polynomial arising from community structure (extended abstract)
• The enumeration of vertex induced subgraphs with respect to the number of components

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)