Bipartite powers of k-chordal graphsReport as inadecuate

Bipartite powers of k-chordal graphs - Download this document for free, or read online. Document in PDF available to download.

1 CSA - Department of Computer Science and Automation Bangalore

Abstract : Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. Brandstädt et al. in Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 1771-3:9-16, 1997. showed that if Gm is k-chordal, then so is Gm+2. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m-th bipartite power Gm of a bipartite graph G is the bipartite graph obtained from G by adding edges u,v where dGu,v is odd and less than or equal to m. Note that Gm = Gm+1 for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is Gm, where k, m are positive integers with k≥4.

Author: Sunil Chandran - Rogers Mathew -



Related documents