✦ LIBER ✦

On the crossing numbers of Cartesian products with trees

✍ Scribed by Drago Bokal

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 204 KB
Volume: 56
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20258

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Zip product was recently used in a note establishing the crossing number of the Cartesian product K~1~,n □ P~m~. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007

📜 SIMILAR VOLUMES

The determining number of a Cartesian pr

The determining number of a Cartesian product

✍ Debra L. Boutin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract A set __S__ of vertices is a determining set for a graph __G__ if every automorphism of __G__ is uniquely determined by its action on __S__. The determining number of __G__, denoted Det(__G__), is the size of a smallest determining set. This paper begins by proving that if __G__=__G__□⋅

On the crossing numbers of products of c

On the crossing numbers of products of cycles and graphs of order four

✍ Lowell W. Beineke; Richard D. Ringeisen 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

On graphs with the maximum number of spa

On graphs with the maximum number of spanning trees

✍ Alexander K. Kelmans 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta

On the Ramsey number of trees versus gra

On the Ramsey number of trees versus graphs with large clique number

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3

On the domination of the products of gra

On the domination of the products of graphs II: Trees

✍ Michael S. Jacobson; Lael F. Kinch 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 377 KB

For a graph G, a subset of vertices D is a dominating set if for each vertex x not in D, x is adjacent to at least one vertex of D. The domination number, y(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H,

Equality and Coequality Relations on the

Equality and Coequality Relations on the Cartesian Product of Sets

✍ Daniel A. Romano 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 433 KB

EQUALITY AND COEQUALITY RELATIONS ON THE CARTESIAN PRODUCT O F SETS by DANEL A . ROMANO in Bihac (Yugoslavia) ## 0. Introduction The foundations on constructive mathematics, in BISHOP'S sense [l], rest on and comprise the three primitive notions of numbers, classes and computations. We believe tha