Article ID Journal Published Year Pages File Type
4649524 Discrete Mathematics 2008 12 Pages PDF
Abstract

The bandwidth B(G)B(G) of a graph G   is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)}max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H  , written as G∘HG∘H, is the graph obtained by taking one copy of G   and |V(G)||V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G   by κ(G)κ(G). Let G be a graph on n   vertices with B(G)=κ(G)=k⩾2B(G)=κ(G)=k⩾2 and let H be a graph of order m  . Let c,pc,p and q   be three integers satisfying 1⩽c⩽k-11⩽c⩽k-1 and n-1=pk+q(1⩽q⩽k). We define hi=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1hi=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,ki=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that B(G∘H)=k(m+1)ifn⩾k(2k-1)m+k+1(=h1+1)andm⩾k-1,k(m+1)-cifhc+1+1⩽n⩽hcandm⩾k-1,bifn⩽(2k-1)m+1(=hk)andm⩾2,kifn⩽2kandm=1.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,