The frequency assignment problem asks for assigning frequencies to transmitters in a wireless network and includes a variety of specific subproblems. In particular, the packing coloring problem comes from the regulations concerning the assignment of broadcast frequencies to radio stations. The problem is placed on a graph-theoretical footing and modeled as the packing chromatic number $\chi_{\rho}(G)$ of a graph $G$. The packing chromatic number of $G$ is the smallest integer $k$ such that the vertex set $V(G)$ can be partitioned into disjoint classes $X_1, . . . , X_k$, with the condition that vertices in $X_i$ have pairwise distance greater than $i$. The determination of the packing chromatic number is known to be \textbf{NP}-hard. This paper presents an integer linear programming model and a satisfiability test model for the packing coloring problem. The proposed models were applied for studying the packing chromatic numbers of Cartesian products of paths and cycles and for the packing chromatic numbers of some distance graphs.
COBISS.SI-ID: 21043464
Let $\rho(G)$ denote the number of convex cycles of a simple graph $G$ of order $n$, size $m$, and girth $3 \leq g \leq n$. It is proved that $\rho(G) \leq \frac{n}{g} (m-n+1)$ and that equality holds if and only if $G$ is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.
COBISS.SI-ID: 17363801
Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph $G$ with $\gamma(G)=3$ and an arbitrary graph $H$, $\gamma(G \Box H) \ge 3\gamma(H)$.
COBISS.SI-ID: 17453401
The b-chromatic index $\varphi'(G)$ of a graph $G$ is the largest integer $k$ such that $G$ admits a proper $k$-edge coloring in which every color class contains at least one edge incident to some edge in all the other color classes. The b-chromatic index of trees is determined and equals either to a natural upper bound $m'(T)$ or one less, where $m'(T)$ is connected with the number of edges of high degree. Some conditions are given for which graphs have the b-chromatic index strictly less than $m'(G)$, and for which conditions it is exactly $m'(G)$. In the last part of the paper regular graphs are considered. It is proved that with four exceptions, the b-chromatic number of cubic graphs is $5$. The exceptions are $K_4$, $K_{3,3}$, the prism over $K_3$, and the cube $Q_3$.
COBISS.SI-ID: 17435225
Motivated by the problem about HOMO-LUMO separation that arises in mathematical chemistry, W. Fowler and T. Pisanski ["HOMO-LUMO maps for fullerenes", Acta Chim. Slov. 57, 513--517 (2010); MATCH Commun. Math. Comput. Chem. 64, No. 2, 373--390 (2010] introduced the notion of the HL-index which measures how large in absolute value may be the median eigenvalues of a graph. In this note we provide rather tight lower and upper bounds on the maximum value of the HL-index among all graphs with given average degree. In particular, we determine the exact value of this parameter when restricted to chemically relevant graphs, i.e. graphs of maximum degree 3, and thus answer a question from [Fowler, Patrick W.; Pisanski, Tomaž: HOMO-LUMO maps for fullerenes, Acta chim. Slov. 57, 513-517 (2010); Fowler, Patrick W.; Pisanski, Tomaž: HOMO-LUMO maps for chemical graphs, MATCH commun. Math. comput. Chem. 64, 373-390 (2010); Jaklič, G.; Fowler, P. W.; Pisanski, T.: HL-index of a graph, Ars math. Contemp. 5, 99-105 (2012)]. The proof provides additional insight about eigenvalue distribution of large subcubic graphs.
COBISS.SI-ID: 17632345