Bipartite Powers of k-chordal Graphs
L. Sunil Chandran, Rogers Mathew
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,
177(1-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 G[m] of a
bipartite graph G is the bipartite graph obtained from
G by adding edges (u,v) where
dG(u,v) is odd and less than or equal to
m. Note that G[m] =
G[m+1] for each odd m. In this paper we
show that, given a bipartite graph G, if G
is k-chordal then so is G[m],
where k, m are positive integers with
k≥4.
Full Text: PDF PostScript