Given two graphs and , assume that and is a subset of . We introduce a new graph operation called the incidence product, denoted by , as follows: insert a new vertex into each edge of , then join with edges those pairs of new vertices on adjacent edges of . Finally, for every vertex , replace it by a copy of the graph
and join every new vertex being adjacent to to every vertex of . It generalizes the line graph operation. We prove that the independence polynomial where is its matching polynomial. Based on this formula, we show that the incidence product of some graphs preserves symmetry, unimodality, reality of zeros of independence polynomials. As applications, we obtain some graphs so-formed having symmetric and unimodal independence polynomials. In particular, the graph introduced by Cvetkovi?, Doob and Sachs has a symmetric and unimodal independence polynomial. 相似文献
The inflation of a graph is obtained from by replacing every vertex of degree by a clique and each edge by an edge between two vertices of the corresponding cliques and of in such a way that the edges of which come from the edges of form a matching of . A set of vertices in a graph is a total dominating set, abbreviated TDS, of if every vertex of is adjacent to a vertex in . The minimum cardinality of a TDS of is the total domination number of . In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if is a connected graph of order , then , and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of to be at least , then we show that , with equality if and only if has a perfect matching. If we increase the minimum degree requirement of to be at least , then we show , with equality if and only if every minimum TDS of is a perfect total dominating set of , where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set. 相似文献
The independence polynomial of a graph is where denotes the number of independent sets of of size (note that ). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees. 相似文献
Let be a graph and let and be positive integers. A subset of the vertex set of is a -dominating set if every vertex not in has at least neighbors in . The -domination number is the cardinality of a smallest -dominating set of . A subset is a -independent set of if every vertex in has at most neighbors in . The -independence number is the cardinality of a largest -independent set of . In this work, we study the interaction between and in a graph . Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on -domination and -independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants. 相似文献
Divided symmetrization of a function is symmetrization of the ratio where the product is taken over the set of edges of some graph . We concentrate on the case when is a tree and is a polynomial of degree , in this case is a constant function. We give a combinatorial interpretation of the divided symmetrization of monomials for general trees and probabilistic game interpretation for a tree which is a path. In particular, this implies a result by Postnikov originally proved by computing volumes of special polytopes, and suggests its generalization. 相似文献
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume is a graph and is a mapping. For a nonnegative integer , let be the extension of to the graph for which for each vertex of . Let be the minimum such that is not -choosable and be the minimum such that is not -paintable. We study the parameter and for arbitrary mappings . For , an -dominated path ending at is a monotonic path of the grid from to such that each vertex on satisfies . Let be the number of -dominated paths ending at . By this definition, the Catalan number equals . This paper proves that if has vertices and , then , where and for . Therefore, if , then equals the Catalan number . We also show that if is the disjoint union of graphs and , then and . This generalizes a result in Carraher et al. (2014), where the case each is a copy of is considered. 相似文献
We consider the action of a real semisimple Lie group G on the complexification of a semisimple symmetric space and we present a refinement of Matsuki?s results (Matsuki, 1997 [1]) in this case. We exhibit a finite set of points in , sitting on closed G-orbits of locally minimal dimension, whose slice representation determines the G-orbit structure of . Every such point lies on a compact torus and occurs at specific values of the restricted roots of the symmetric pair . The slice representation at is equivalent to the isotropy representation of a real reductive symmetric space, namely . In principle, this gives the possibility to explicitly parametrize all G-orbits in . 相似文献
The vertex arboricity of a graph is the minimum number of colors required to color the vertices of such that no cycle is monochromatic. The list vertex arboricity is the list-coloring version of this concept. In this note, we prove that if is a toroidal graph, then ; and if and only if contains as an induced subgraph. 相似文献