Profile minimization on products of graphs
Journal
Discrete Mathematics
Journal Volume
306
Journal Issue
8-9
Pages
792-800
Date Issued
2006
Author(s)
Abstract
The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as{A formula is presented}where f runs over all bijections from V ( G ) to { 1, 2, ..., | V ( G ) | } and N [ v ] = { v } ∪ { x ∈ V ( G ) : xv ∈ E ( G ) }. The main result of this paper is to determine the profiles of Km × Kn, Ks, t × Kn and Pm × Kn. © 2006 Elsevier B.V. All rights reserved.
Type
journal article