Page 1 Next

Displaying 1 – 20 of 22

Showing per page

A Note on a Broken-Cycle Theorem for Hypergraphs

Martin Trinks (2014)

Discussiones Mathematicae Graph Theory

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

A Note on the Permanental Roots of Bipartite Graphs

Heping Zhang, Shunyi Liu, Wei Li (2014)

Discussiones Mathematicae Graph Theory

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...

Bipartition Polynomials, the Ising Model, and Domination in Graphs

Markus Dod, Tomer Kotek, James Preen, Peter Tittmann (2015)

Discussiones Mathematicae Graph Theory

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....

Exact Expectation and Variance of Minimal Basis of Random Matroids

Wojciech Kordecki, Anna Lyczkowska-Hanćkowiak (2013)

Discussiones Mathematicae Graph Theory

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).

Extremal Matching Energy of Complements of Trees

Tingzeng Wu, Weigen Yan, Heping Zhang (2016)

Discussiones Mathematicae Graph Theory

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...

Matroids over a ring

Alex Fink, Luca Moci (2016)

Journal of the European Mathematical Society

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 = , 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...

On rational radii coin representations of the wheel graph

Geir Agnarsson, Jill Bigley Dunham (2013)

Discussiones Mathematicae - General Algebra and Applications

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...

On the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph

Ji-Ming Guo, Jianxi Li, Wai Chee Shiu (2013)

Czechoslovak Mathematical Journal

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....

On the spectral radius of -shape trees

Xiaoling Ma, Fei Wen (2013)

Czechoslovak Mathematical Journal

Let A ( G ) 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 φ ( G , λ ) or simply φ ( G ) . The spectrum of G consists of the roots (together with their multiplicities) λ 1 ( G ) λ 2 ( G ) ... λ n ( G ) of the equation φ ( G , λ ) = 0 . The largest root λ 1 ( G ) 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 ) ...

Some properties of the distance Laplacian eigenvalues of a graph

Mustapha Aouchiche, Pierre Hansen (2014)

Czechoslovak Mathematical Journal

The distance Laplacian of a connected graph G is defined by = Diag ( Tr ) - 𝒟 , where 𝒟 is the distance matrix of G , and Diag ( Tr ) is the diagonal matrix whose main entries are the vertex transmissions in G . The spectrum of is called the distance Laplacian spectrum of G . In the present paper, we investigate some particular distance Laplacian eigenvalues. Among other results, we show that the complete graph is the unique graph with only two distinct distance Laplacian eigenvalues. We establish some properties of the distance...

Currently displaying 1 – 20 of 22

Page 1 Next