On the complexity of a class of pyramid graphs and Chebyshev polynomials

DOI10.1155/2013/820549MaRDI QIDQ474169zbMATH OpenOpenAlexWikidataFDO

Authors S. N. Daoud

Publication date 24 November 2014

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2013/820549

Mathematics Subject Classification ID

Graph polynomials (05C31) Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

Summary: In mathematics, one always tries to get new structures from given ones. This also applies to the realm of graphs, where one can generate many new graphs from a given set of graphs. In this paper we define a class of pyramid graphs and derive simple formulas of the complexity, number of spanning trees, of these graphs, using linear algebra, Chebyshev polynomials, and matrix analysis techniques.

Recommendations

• The complexity of some classes of pyramid graphs created from a gear graph
• Chebyshev polynomials and spanning tree formulas
• The number of spanning trees in some classes of graphs
• Chebyshev polynomials and formulas for a number of spanning trees in circulant graphs
• Number of spanning trees of different products of complete and complete bipartite graphs

Cites work

• A certain polynomial of a graph and graphs with an extremal number of trees
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• Spanning tree formulas and Chebyshev polynomials
• The number of spanning trees in a prism

Cited in

(3)

• Number of spanning trees of different products of complete and complete bipartite graphs
• Small \(k\)-pyramids and the complexity of determining \(k\)
• The complexity of some classes of pyramid graphs created from a gear graph

This page was built for publication: On the complexity of a class of pyramid graphs and Chebyshev polynomials

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