✦ LIBER ✦

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

✍ Scribed by Brian Jacobson; Andrew Niedermaier; Victor Reiner

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 147 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10139

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs $K_{n_{1},\ldots, {n_k}}$, we describe the critical group structure completely. For Cartesian products of complete graphs $K_{n_{1}} \times \cdots \times K_{n_{k}}$, we generalize results of H. Bai on the k‐dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p‐primary structure for all primes p that divide none of $n_1, \ldots, n_k$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003

📜 SIMILAR VOLUMES

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

Factorizations of complete multipartite

Factorizations of complete multipartite graphs into generalized cubes

✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite

Maximal sets of hamilton cycles in compl

Maximal sets of hamilton cycles in complete multipartite graphs

✍ Mike Daven; J. A. MacDougall; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

## Abstract A set __S__ of edge‐disjoint hamilton cycles in a graph __G__ is said to be __maximal__ if the edges in the hamilton cycles in __S__ induce a subgraph __H__ of __G__ such that __G__ − __E__(__H__) contains no hamilton cycles. In this context, the spectrum __S__(__G__) of a graph __G__ i

Nondisconnecting disentanglements of ama

Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs

✍ C. D. Leach; C. A. Rodger 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract In this paper necessary and sufficient conditions are found for an edge‐colored graph __H__ to be the homomorphic image of a 2‐factorization of a complete multipartite graph __G__ in which each 2‐factor of __G__ has the same number of components as its corresponding color class in __H__

Tenacity of complete graph products and

Tenacity of complete graph products and grids

✍ Choudum, S. A.; Priya, N. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB 👁 2 views

Computer or communication networks are so designed that they do not easily get disrupted under external attack and, moreover, these are easily reconstructible if they do get disrupted. These desirable properties of networks can be measured by various parameters like connectivity, toughness, integrit

Decomposing complete multipartite graphs

Decomposing complete multipartite graphs into closed trails of arbitrary even lengths

✍ Benjamin R. Smith; Selda Küçükçifçi; Emineşule Yazıcı 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

We prove that any complete multipartite graph with parts of even size can be decomposed into closed trails with prescribed even lengths.