Graph polynomials

DOI10.5402/2011/193560MaRDI QIDQ643157zbMATH OpenOpenAlexWikidataFDO

Authors Mehdi Alaeiyan, Saeid Mohammadian

Publication date 28 October 2011

Published in ISRN Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.5402/2011/193560

zbMATH Keywords

binary programminglinear programming

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Linear programming (90C05)

Review text

Summary: One of the most important and applied concepts in graph theory is to find the edge cover, vertex cover, and dominating sets with minimum cardinal also to find independence and matching sets with maximum cardinal and their polynomials. Although there exist some algorithms for finding some of them, but in this paper we want to study all of these concepts from viewpoint linear and binary programming and we compute the coefficients of the polynomials by solving a system of linear equations with \(\{0, 1\}\) variables.

Recommendations

• Linear programming and primal-dual problems in graph theory
• Graph polynomials
• An algorithm for calculating the independence and vertex-cover polynomials of a graph
• On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs
• On the characteristic polynomials of covering number of vertices and edges of graphs

Cites work

• Constant-time distributed dominating set approximation
• scientific article; zbMATH DE number 854567 (Why is no real title available?)

Cited in

(4)

• Polynomials on graphs
• Graph-polynomials
• Linear programming and primal-dual problems in graph theory
• scientific article; zbMATH DE number 6378508 (Why is no real title available?)

This page was built for publication: Graph polynomials

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