Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWeighted Graph Colorings
143
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study two weighted graph coloring problems, in which one assigns $q$ colors to the vertices of a graph such that adjacent vertices have different colors, with a vertex weighting $w$ that either disfavors or favors a given color. We exhibit a weighted chromatic polynomial $Ph(G,q,w)$ associated with this problem that generalizes the chromatic polynomial $P(G,q)$. General properties of this polynomial are proved, and illustrative calculations for various families of graphs are presented. We show that the weighted chromatic polynomial is able to distinguish between certain graphs that yield the same chromatic polynomial. We give a general structural formula for $Ph(G,q,w)$ for lattice strip graphs $G$ with periodic longitudinal boundary conditions. The zeros of $Ph(G,q,w)$ in the $q$ and $w$ planes and their accumulation sets in the limit of infinitely many vertices of $G$ are analyzed. Finally, some related weighted graph coloring problems are mentioned.
rate research
Read More
Osculating paths are sets of directed lattice paths which are not allowed to cross each other or have common edges, but are allowed to have common vertices. In this work we derive a constant term formula for the number of such lattice paths by solving a set of simultaneous difference equations.
We examine the groundstate wavefunction of the rotor model for different boundary conditions. Three conjectures are made on the appearance of numbers enumerating alternating sign matrices. In addition to those occurring in the O($n=1$) model we find the number $A_{rm V}(2m+1;3)$, which 3-enumerates vertically symmetric alternating sign matrices.
The $mathcal{PT}-$symmetric quantum mechanical $V=ix^3$ model over the real line, $xinmathbb{R}$, is infrared (IR) truncated and considered as Sturm-Liouville problem over a finite interval $xinleft[-L,Lright]subsetmathbb{R}$. Via WKB and Stokes graph analysis, the location of the complex spectral branches of the $V=ix^3$ model and those of more general $V=-(ix)^{2n+1}$ models over $xinleft[-L,Lright]subsetmathbb{R}$ are obtained. The corresponding eigenvalues are mapped onto $L-$invariant asymptotic spectral scaling graphs $mathcal{R}subset mathbb{C}$. These scaling graphs are geometrically invariant and cutoff-independent so that the IR limit $Lto infty $ can be formally taken. Moreover, an increasing $L$ can be associated with an $mathcal{R}-$constrained spectral UV$to$IR renormalization group flow on $mathcal{R}$. The existence of a scale-invariant $mathcal{PT}$ symmetry breaking region on each of these graphs allows to conclude that the unbounded eigenvalue sequence of the $ix^3$ Hamiltonian over $xinmathbb{R}$ can be considered as tending toward a mapped version of such a $mathcal{PT}$ symmetry breaking region at spectral infinity. This provides a simple heuristic explanation for the specific eigenfunction properties described in the literature so far and clear complementary evidence that the $mathcal{PT}-$symmetric $V=-(ix)^{2n+1}$ models over the real line $xinmathbb{R}$ are not equivalent to Hermitian models, but that they rather form a separate model class with purely real spectra. Our findings allow us to hypothesize a possible physical interpretation of the non-Rieszian mode behavior as a related mode condensation process.
We propose a new approach for defining and searching clusters in graphs that represent real technological or transaction networks. In contrast to the standard way of finding dense parts of a graph, we concentrate on the structure of edges between the clusters, as it is motivated by some earlier observations, e.g. in the structure of networks in ecology and economics and by applications of discrete tomography. Mathematically special colorings and chromatic numbers of graphs are studied.
Maximum entropy null models of networks come in different flavors that depend on the type of constraints under which entropy is maximized. If the constraints are on degree sequences or distributions, we are dealing with configuration models. If the degree sequence is constrained exactly, the corresponding microcanonical ensemble of random graphs with a given degree sequence is the configuration model per se. If the degree sequence is constrained only on average, the corresponding grand-canonical ensemble of random graphs with a given expected degree sequence is the soft configuration model. If the degree sequence is not fixed at all but randomly drawn from a fixed distribution, the corresponding hypercanonical ensemble of random graphs with a given degree distribution is the hypersoft configuration model, a more adequate description of dynamic real-world networks in which degree sequences are never fixed but degree distributions often stay stable. Here, we introduce the hypersoft configuration model of weighted networks. The main contribution is a particular version of the model with power-law degree and strength distributions, and superlinear scaling of strengths with degrees, mimicking the properties of some real-world networks. As a byproduct, we generalize the notions of sparse graphons and their entropy to weighted networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
