Discrete Mathematics 313 (2013) 2115–2118
Contents lists available at SciVerse ScienceDirect
Discrete Mathematics
journal homepage: www.elsevier.com/locate/disc
Note
l
1
-embeddability under the edge-gluing operation on graphs
Guangfu Wang
a,∗
, Heping Zhang
b
a
School of Basic Science, East China Jiaotong University, Nanchang, Jiangxi 330013, China
b
School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, China
a r t i c l e i n f o
Article history:
Received 12 May 2012
Received in revised form 27 April 2013
Accepted 29 April 2013
Available online 22 May 2013
Keywords:
Hypercube
l
1
-graph
Edge-gluing operation
a b s t r a c t
A graph is an l
1
-graph if its vertices can be labeled by binary vectors in such a way that the
Hamming distance between the binary addresses is, up to scale, the distance in the graph
between the corresponding vertices. In this note, we study when the result of gluing two
l
1
-graphs along an edge is an l
1
-graph. If at least one of the constituent graphs is bipar-
tite, then the resulting graph is also an l
1
-graph. For two nonbipartite l
1
-graphs, this is not
always the case.
© 2013 Elsevier B.V. All rights reserved.
1. Introduction
All graphs considered in this note are finite, unoriented, without loops and multiple edges. For a graph G, let V (G) and
E(G) denote its vertex set and edge set, respectively. The distance d
G
(u, v) between two vertices u and v of G is the length of
a shortest path between u and v. If the graph G is clear from the context, then we will simply use d(u, v). Terminology not
defined here can be found in [16].
Let X denote the set of all real sequences x such that
∞
k=1
|x
k
| < ∞, where x = (x
1
, x
2
, . . .). Define the distance function
d
1
on X as d
1
(x, y) =
∞
k=1
|x
k
− y
k
| for x, y ∈ X. It is known that (X, d
1
) is a metric space and it is called the l
1
-space. If
Y ⊆ X and Y is a linear space, then (Y , d
1
) is a subspace of the l
1
-space.
A graph G is an l
1
-graph (or l
1
-embeddable) if and only if (V (G), d
G
) is isomorphic to a subspace of the l
1
-space. That is,
there exists a distance-preserving mapping φ from V (G) into X such that d
G
(x, y) = d
1
(φ(x), φ(y)) for x, y ∈ V (G) [12].
The n-dimensional hypercube or n-cube Q
n
is defined as follows: The vertex set consists of all n-tuples b
1
, . . . , b
n
with
b
i
∈ {0, 1}, and two vertices are adjacent if and only if the corresponding n-tuples differ in precisely one position.
Assouad and Deza [1] showed that a graph G is an l
1
-graph if and only if it is scale-λ-embeddable into a hypercube Q
n
for
some positive integers λ and n, meaning that there is a mapping ϕ : V (G) → V (Q
n
) such that
λ · d
G
(x, y) = d
Q
n
(ϕ(x), ϕ(y))
for x, y ∈ V (G). The integer λ is a scale of G. The smallest such integer λ is called the minimum scale of G. If λ = 1, then G is
an isometric subgraph of Q
n
(also known as a partial cube). By Deza and Laurent [10, Lemma 21.1.2], the minimum scale λ of
G is equal to 1 or is even.
Deza and Grishukhin [7] and Shpectorov [17] characterized l
1
-graphs, respectively: a graph is an l
1
-graph if and only
if it is an isometric subgraph of a Cartesian product of cocktail party graphs and halved cubes. The cocktail party graph
K
k×2
is a complete multipartite graph with k parts, each of cardinality 2. The hypercube is bipartite, and the halved cube is
the graph defined on one of the parts, where the adjacency relation is given by being distance 2 apart in the hypercube.
∗
Corresponding author.
E-mail addresses: wguangfu@yahoo.com, wgfmath@126.com (G. Wang), zhanghp@lzu.edu.cn (H. Zhang).
0012-365X/$ – see front matter © 2013 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.disc.2013.04.032
下载后可阅读完整内容，剩余3页未读，立即下载
weixin_38743084
- 粉丝: 12
- 资源: 931
我的内容管理
展开
最新资源
- 多传感器数据融合手册：国外原版技术指南
- MyEclipse快捷键大全，提升编程效率
- 从零开始的编程学习：Linux汇编语言入门
- EJB3.0实例教程：从入门到精通
- 深入理解jQuery源码：解析与分析
- MMC-1电机控制ASSP芯片用户手册
- HS1101相对湿度传感器技术规格与应用
- Shell基础入门：权限管理与常用命令详解
- 2003年全国大学生电子设计竞赛：电压控制LC振荡器与宽带放大器
- Android手机用户代理(User Agent)详解与示例
- Java代码规范：提升软件质量和团队协作的关键
- 浙江电信移动业务接入与ISAG接口实战指南
- 电子密码锁设计：安全便捷的新型锁具
- NavTech SDAL格式规范1.7版：车辆导航数据标准
- Surfer8中文入门手册：绘制等高线与克服语言障碍
- 排序算法全解析：冒泡、选择、插入、Shell、快速排序
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
