Search

Abstract: For each non-negative integer , we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most . Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth. [Copyright &y& Elsevier]

Abstract: We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors. [Copyright &y& Elsevier]

Abstract: Let be a finite, simple and undirected graph. For , let be the edge boundary of . Given an integer , , let the edge isoperimetric value of at be defined as . The edge isoperimetric peak of is defined as . Let denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete -ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete -ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth (denoted as ), and where , are constants. For a complete -ary tree of depth (denoted as ) and where is a constant, we show that and where , are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete -ary tree. Let be a finite, connected and rooted tree — the root being the vertex . Define a weight function where the weight of a vertex is the number of its successors (including itself) and let the weight index be defined as the number of distinct weights in the tree, i.e . For a positive integer , let . We show that . [Copyright &y& Elsevier]

Abstract: The d-dimensional hypercube, , is the graph on vertices, which correspond to the d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the d-vectors where the components are from the set , and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the . [Copyright &y& Elsevier]

In this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between ⌈3(k−1)/2⌉ and 3⌈k/2⌉. [Copyright &y& Elsevier]