We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte ...polynomial, matching polynomials, interlace polynomials, and the cover polynomial of digraphs. We introduce two classes of (hyper)graph polynomials definable in second order logic, and outline a research program for their classification in terms of definability and complexity considerations, and various notions of reducibilities.
Subgraphs can results through application of criteria based on matrix which characterize the entire graph. The most important categories of criteria are the ones able to produce connected subgraphs ...(fragments). Based on theoretical frame on graph theory, the fragmentation algorithm on pair of vertices containing the largest fragments (called MaxF) are exemplified. The counting polynomials are used to enumerate number of all connected substructures and their sizes. For a general class of graphs called dendrimers general formulas giving counting polynomials are obtained and characterized using informational measures.
In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external ...field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.
Coloring Rings in Species White, Jacob
Discrete Mathematics and Theoretical Computer Science,
01/2014, Letnik:
DMTCS Proceedings vol. AT,..., Številka:
Proceedings
Journal Article, Conference Proceeding
Recenzirano
Odprti dostop
We present a generalization of the chromatic polynomial, and chromatic symmetric function, arising in the study of combinatorial species. These invariants are defined for modules over lattice rings ...in species. The primary examples are graphs and set partitions. For these new invariants, we present analogues of results regarding stable partitions, the bond lattice, the deletion-contraction recurrence, and the subset expansion formula. We also present two detailed examples, one related to enumerating subgraphs by their blocks, and a second example related to enumerating subgraphs of a directed graph by their strongly connected components.
A graph polynomial
q
(
G
;
ζ
)
has recently been studied by Arratia et al. The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete ...Mathematics, San Francisco, CA, 2000, North-Holland, Amsterdam, pp. 237–245. That polynomial can be derived from the restricted Tutte–Martin polynomial of an isotropic system, which we introduced A. Bouchet, Tutte–Martin polynomials and orienting vectors of isotropic systems, Graphs Combin. 7 (1991) 235–252 in order to prove a conjecture of Las Vergnas on the Tutte polynomial of a binary matroid. It follows that (i)
|
q
(
G
;
-
1
)
|
is equal to a power of 2 and (ii)
q
(
G
;
3
)
is the same power of 2 times an odd integer. Neither (i) or (ii) appears in R. Arratia et al., The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Mathematics, San Francisco, CA, 2000, North-Holland, Amsterdam, pp. 237–245.
The coloured Tutte polynomial by Bollobás and Riordan is, as a generalization of the Tutte polynomial, the most general graph polynomial for coloured graphs that satisfies certain ...contraction-deletion identities. Jaeger, Vertigan, and Welsh showed that the classical Tutte polynomial is
#P
-hard to evaluate almost everywhere by establishing reductions along curves and lines.
We establish a similar result for the coloured Tutte polynomial on integral domains. To capture the algebraic flavour and the uniformity inherent in this type of result, we introduce a new kind of reductions,
uniform algebraic reductions
, that are well-suited to investigate the evaluation complexity of graph polynomials. Our main result identifies a small, algebraic set of exceptional points and says that the evaluation problem of the coloured Tutte is equivalent for all non-exceptional points, under polynomial-time uniform algebraic reductions. On the way we obtain a self-contained proof for the difficult evaluations of the classical Tutte polynomial.
Subgraphs can results through application of criteria based on matrix which characterize the entire graph. The most important categories of criteria are the ones able to produce connected subgraphs ...(fragments). Theoretical frame on graph theory, a series of three molecular fragmentation algorithms on pair of atoms, and construction of four square matrices (Szeged, Cluj, MaxF, and CMaxF) containing the fragment's size are presented. New theoretical results on fragment's size and the order based on sizes are presented. The obtained matrices were used to obtain the counting polynomials for two series of regular structures. The informational analysis on the obtained distinct counting polynomials was performed by using informational entropy and energy. Structure-property relationship analysis has been also conducted on the obtained counting polynomials. The obtained results are discussed and the main conclusions are highlighted. PUBLICATION ABSTRACT
PDF
