We introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs ?$G$? with a fair reception of size ?$\gamma(G)$? satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well-known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture.
COBISS.SI-ID: 15170393
The packing chromatic number \chi_\rho(G) of a graph G is the smallest integer k such that the vertex set V(G) can be partitioned into disjoint classes X_1,...,X_k, where vertices in X_i have pairwise distance greater than i. For the Cartesian product of a path and the two-dimensional square lattice it is proved that \chi_\rho(P_m \square {\mathbb{Z}}^2) = \infty for any m \ge 2. Moreover, it is shown that \chi_\rho(G \square{\mathbb{Z}}) ( \infty for any finite graph G.
COBISS.SI-ID: 15146585
We study (cyclic) Gray codes avoiding a given set of faulty edges that form a matching. Given a matching M and two vertices u,v of Qn, n)=4, our result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for M, for the existence of a Gray code between u and v that avoids M.
COBISS.SI-ID: 15521369
We show that, for any fixed constant k, the sum of the distances between all pairs of vertices of an abstract graphs with n vertices and treewidth at most k can be computed in O(n log^{k-1}n) time. We also show that, for any fixed constant k, the dilation of a geometric graph (i.e., a graph drawn in the) plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(n log^{k+1} n) expected time.
COBISS.SI-ID: 15160409
The main result of this paper proves that every large enough graph, whose connectivity is linear in terms of a parameter t, contains the complete bipartite graph K(t,k) (for any constant k) as a minor. This result has numerous important consequences; among others resolves a problem of Mader from 1970's and a conjecture of Thomason from 1982.
COBISS.SI-ID: 15145049