|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Colorations, Orthotopes, and a Huge Polynomial Tutte Invariant of Weighted Gain Graphs | | David Forge
; Thomas Zaslavsky
; | | Date: |
26 Jun 2013 | | Abstract: | A gain graph is a graph whose edges are labelled invertibly from a group. A
weighted gain graph is a gain graph with vertex weights from a semigroup, where
the gain group is lattice ordered and acts on the weight semigroup. For
weighted gain graphs we establish basic properties and we present general
dichromatic and tree-expansion polynomials that are Tutte invariants (they
satisfy Tutte’s deletion-contraction and multiplicative identities). Our
dichromatic polynomial includes the classical graph one by Tutte, Zaslavsky’s
for gain graphs, Noble and Welsh’s for graphs with positive integer weights,
and that of rooted integral gain graphs by Forge and Zaslavsky. It is unusual
in sometimes having uncountably many variables, in contrast to other known
Tutte invariants that have at most countably many variables, and in not being
itself a universal Tutte invariant of weighted gain graphs; that remains to be
found.
An evaluation of our polynomial counts proper colorations of the gain graph
when the vertex weights are lists of permissible colors from a color set with a
gain-group action. When the gain group is Z^d, the lists are order ideals in
the integer lattice Z^d, and there are specified upper bounds on the colors,
then there is a formula for the number of bounded proper colorations that is a
piecewise polynomial function, of degree d|V|, of the upper bounds. This
example leads to graph-theoretical formulas for the number of integer lattice
points in an orthotope but outside a finite number of affinographic
hyperplanes, and for the number of n x d integral matrices that lie between two
specified matrices but not in any of certain subspaces defined by simple row
equations. | | Source: | arXiv, 1306.6132 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER