Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDomination Polynomials of Graph Products
242
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various products, ranging from explicit formulae and recurrences for specific families to more general results. As an application, we show the domination polynomial is computationally hard to evaluate.
rate research
Read More
The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this paper representations of D(G,x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G,x) as a sum ranging over spanning bipartite subgraphs of G. We call a graph G conformal if all of its components are of even order. We show that the number of dominating sets of G equals a sum ranging over vertex-induced conformal subgraphs of G.
For a graph $G,$ we consider $D subset V(G)$ to be a porous exponential dominating set if $1le sum_{d in D}$ $left( frac{1}{2} right)^{text{dist}(d,v) -1}$ for every $v in V(G),$ where dist$(d,v)$ denotes the length of the smallest $dv$ path. Similarly, $D subset V(G)$ is a non-porous exponential dominating set is $1le sum_{d in D} left( frac{1}{2} right)^{overline{text{dist}}(d,v) -1}$ for every $v in V(G),$ where $overline{text{dist}}(d,v)$ represents the length of the shortest $dv$ path with no internal vertices in $D.$ The porous and non-porous exponential dominating number of $G,$ denoted $gamma_e^*(G)$ and $gamma_e(G),$ are the minimum cardinality of a porous and non-porous exponential dominating set, respectively. The consecutive circulant graph, $C_{n, [ell]},$ is the set of $n$ vertices such that vertex $v$ is adjacent to $v pm i mod n$ for each $i in [ell].$ In this paper we show $gamma_e(C_{n, [ell]}) = gamma_e^*(C_{n, [ell]}) = leftlceil tfrac{n}{3ell +1} rightrceil.$
In 2009, Brown gave a set of conditions which when satisfied imply that a Feynman integral evaluates to a multiple zeta value. One of these conditions is called reducibility, which loosely says there is an order of integration for the Feynman integral for which Browns techniques will succeed. Reducibility can be abstracted away from the Feynman integral to just being a condition on two polynomials, the first and second Symanzik polynomials. These polynomials can be defined from graphs, and thus reducibility is a property of graphs. We prove that for a fixed number of external momenta and no masses, reducibility is graph minor closed, correcting the previously claimed proofs of this fact. A computational study of reducibility was undertaken by Bogner and L{u}ders who found that for graphs with $4$-on-shell momenta and no masses, $K_{4}$ with momenta on each vertex is a forbidden minor. We add to this and find that when we restrict to graphs with four on-shell external momenta the following graphs are forbidden minors: $K_{4}$ with momenta on each vertex, $W_{4}$ with external momenta on the rim vertices, $K_{2,4}$ with external momenta on the large side of the bipartition, and one other graph. We do not expect that these minors characterize reducibility, so instead we give structural characterizations of the graphs not containing subsets of these minors. We characterize graphs not containing a rooted $K_{4}$ or rooted $W_{4}$ minor, graphs not containing rooted $K_{4}$ or rooted $W_{4}$ or rooted $K_{2,4}$ minors, and also a characterization of graphs not containing all of the known forbidden minors. Some comments are made on graphs not containing $K_{3,4}$, $K_{6}$ or a graph related to Wagners graph as a minor.
We define the type of graph products, which enable us to treat many graph products in a unified manner. These unified graph products are shown to be compatible with Godsil--McKay switching. Furthermore, by this compatibility, we show that the Doob graphs can also be obtained from the Hamming graphs by switching.
A k-valuation is a special type of edge k-colouring of a medial graph. Various graph polynomials, such as the Tutte, Penrose, Bollobas-Riordan, and transition polynomials, admit combinatorial interpretations and evaluations as weighted counts of k-valuations. In this paper, we consider a multivariate generating function of k-valuations. We show that this is a polynomial in k and hence defines a graph polynomial. We then show that the resulting polynomial has several desirable properties, including a recursive deletion-contraction-type definition, and specialises to the graph polynomials mentioned above. It also offers an alternative extension of the Penrose polynomial from plane graphs to graphs in other surfaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
