We introduce and investigate bucolic complexes, a common generalization of systolic complexes and CAT(0) cubical complexes. They are defined as simply connected prism complexes satisfying some local combinatorial conditions. We study various approaches to bucolic complexes: from graph-theoretic and topological perspectives, as well as from the point of view of geometric group theory. In particular, we characterize bucolic complexes by some properties of their 2-skeleta and 1-skeleta (that we call bucolic graphs), by which several known results are generalized. We also show that locally-finite bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties.
COBISS.SI-ID: 16633177
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 paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.
COBISS.SI-ID: 16083801
Handbook of product graphs, second edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and algorithms new to the second edition: (1) Cancellation results, (2) A quadratic recognition algorithm for partial cubes, (3) Results on the strong isometric dimension, (4) Computing the Wiener index via canonical isometric embedding, (5) Connectivity results, (6) A fractional version of Hedetniemi's conjecture, (7) Results on the independence number of Cartesian powers of vertex-transitive graphs, (8) Verification of Vizing's conjecture for chordal graphs, (9) Results on minimum cycle bases and (10) Numerous selected recent results, such as complete minors and nowhere-zero flows. The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the book's website, which can be reached via the authors' home pages.
COBISS.SI-ID: 15916121
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained by Baker, Eppstein, and others, and it generalizes a similar result for "compression" (a variant of contraction) in planar graphs (Klein). Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing many previous algorithms. We also highlight the only main difficulty in extending our results to general $H$-minor-free graphs.
COBISS.SI-ID: 15802457
We show that, for any fixed constant k )= 3, 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 )= 2, 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. Recall that the dilation (or stretch-factor) of a geometric graph is the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance. The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.
COBISS.SI-ID: 15160409