Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there

It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing...

This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants....

We introduce a new concept namely the degree polynomial for the vertices of a simple graph. This notion leads to a concept, namely, the degree polynomial sequence which is stronger than the concept of degree sequence. After obtaining the degree polynomial sequence for some well-known graphs, we prove a theorem which gives a necessary condition for the realizability of a sequence of polynomials with positive integer coefficients. Also we calculate the degree polynomial for the vertices of the join,...

We formulate and prove a formula to compute the expected value of the minimal random basis of an arbitrary finite matroid whose elements are assigned weights which are independent and uniformly distributed on the interval [0, 1]. This method yields an exact formula in terms of the Tutte polynomial. We give a simple formula to find the minimal random basis of the projective geometry PG(r − 1, q).

Gutman and Wagner proposed the concept of the matching energy which is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. And they pointed out that the chemical applications of matching energy go back to the 1970s. Let T be a tree with n vertices. In this paper, we characterize the trees whose complements have the maximal, second-maximal and minimal matching energy. Furthermore, we determine the trees with edge-independence number p whose complements have...

We give a graph theoretic interpretation of $r$-Lah numbers, namely, we show that the $r$-Lah number ${⌊\genfrac{}{}{0pt}{}{n}{k}⌋}_r$ counting the number of $r$-partitions of an $(n+r)$-element set into $k+r$ ordered blocks is just equal to the number of matchings consisting of $n-k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n+2r-1$ ($0\le k\le n$, $r\ge 1$). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$-Stirling numbers of the second kind.

We introduce the notion of a matroid $M$ over a commutative ring $R$, assigning to every subset of the ground set an $R$-module according to some axioms. When $R$ is a field, we recover matroids. When $R=\mathbb{Z}$, and when $R$ is a DVR, we get (structures which contain all the data of) quasi-arithmetic matroids, and valuated matroids, i.e. tropical linear spaces, respectively. More generally, whenever $R$ is a Dedekind domain, we extend all the usual properties and operations holding for matroids (e.g., duality), and...

A flower is a coin graph representation of the wheel graph. A petal of a flower is an outer coin connected to the center coin. The results of this paper are twofold. First we derive a parametrization of all the rational (and hence integer) radii coins of the 3-petal flower, also known as Apollonian circles or Soddy circles. Secondly we consider a general n-petal flower and show there is a unique irreducible polynomial Pₙ in n variables over the rationals ℚ, the affine variety of which contains the...

The Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph are the characteristic polynomials of its Laplacian matrix, signless Laplacian matrix and normalized Laplacian matrix, respectively. In this paper, we mainly derive six reduction procedures on the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph which can be used to construct larger Laplacian, signless Laplacian and normalized Laplacian cospectral graphs, respectively....

Let $A\left(G\right)$ be the adjacency matrix of $G$. The characteristic polynomial of the adjacency matrix $A$ is called the characteristic polynomial of the graph $G$ and is denoted by $\phi (G,\lambda )$ or simply $\phi \left(G\right)$. The spectrum of $G$ consists of the roots (together with their multiplicities) ${\lambda }_1\left(G\right)\ge {\lambda }_2\left(G\right)\ge ...\ge {\lambda }_n\left(G\right)$ of the equation $\phi (G,\lambda )=0$. The largest root ${\lambda }_1\left(G\right)$ is referred to as the spectral radius of $G$. A $‡$-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by $G(l_1,l_2,...,l_7)$$...$