✦ LIBER ✦

The determining number of a Cartesian product

✍ Scribed by Debra L. Boutin

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 118 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20368

No coin nor oath required. For personal study only.

✦ Synopsis

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□⋅□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q~n~)=⌈log~2~n⌉+1 which matches the lower bound, and that Det(K)=⌈log~3~(2__n__+1)⌉+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(H^n^)=Θ(log__n__). © 2009 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

On the crossing numbers of Cartesian pro

On the crossing numbers of Cartesian products with trees

✍ Drago Bokal 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

## 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 metho

The Cartesian product of hypergraphs

✍ Lydia Ostermeier; Marc Hellmuth; Peter F. Stadler 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs

Game coloring the Cartesian product of g

Game coloring the Cartesian product of graphs

✍ Xuding Zhu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

## Abstract This article proves the following result: Let __G__ and __G__′ be graphs of orders __n__ and __n__′, respectively. Let __G__^\*^ be obtained from __G__ by adding to each vertex a set of __n__′ degree 1 neighbors. If __G__^\*^ has game coloring number __m__ and __G__′ has acyclic chromat

Determining the Monogeneity of a Quartic

Determining the Monogeneity of a Quartic Number Field

✍ David Koppenhöfer 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB

This note presents a method that determines all power integral bases of a quartic number field by solving Thue equations of degrees 3 and 4. To this end, projective representations of the ring of integers by graded complete intersections are studied and a criterion for monogeneity in terms of projec

An Inequality on the Size of a Set in a

An Inequality on the Size of a Set in a Cartesian Product

✍ H. Maehara 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 136 KB

Let be a finite subset of the Cartesian product W 1 × • • • × W n of n sets. For A ⊂ {1, 2, . . . , n}, denote by A the projection of onto the Cartesian product of W i , i ∈ A. Generalizing an inequality given in an article by Shen, we prove that , 2, . . . , n}. This inequality is applied to give s

Determination of the Neutralization Numb

Determination of the Neutralization Number for Biodiesel Fuel Production

✍ Komers, Karel ;Skopal, František ;Stloukal, Radek 📂 Article 📅 1997 🏛 John Wiley and Sons ⚖ 438 KB

## Abstract The titration methods used for the determination of the Neutralization Number for biodiesel fuel production are discussed. Two new methods determining strong acids and free fatty acids in one measurement separately are described, one method (of main interest) with potentiometric indicat