图的l1-嵌入相关问题研究

Metric is a basic concept in analysis and it is in the core of the research in graph theory. Metric embeddings is a useful ingredient in the design and analysis of algorithms in operational research, theoretical chemestry, computer science, and so on. The project mainly study the isometric embeddings and distortion of graphic metric space into l1-space. It concerns the following problems: firstly, explore the condition of l1-embeddability of the graph obtained by gluing two non-bipartite l1-graphs along an edge; study the l1-embeddability of the line graph L(G) of a graph G, find out the graphs such that both G and L(G) are l1-embeddable; secondly, find forbidden isometric subgraphs to characterize the structure of l1-graphs; thirdly, study the l1-embeddability of quadrilateral tiling graphs embedded in cylinder, and study the distortion of l1-embeddings of quadrilateral (or hexagonal) tiling graphs embedded in a cylinder(or Mobius strip) ; fourthly, study the hypercube embedding and median of resonance graph of graphs embedded in a surface. The project combines graph theory with analysis, geometry, topology, algebra, etc. This study aims to further enrich and develop the l1-embeddable theories of graph, and the results of embeddings of discrete metric space are helpful to the research of graphic metric space embedding in analytical science.

度量是分析学中的基本概念, 同时也是图论比较核心的研究对象。度量空间的嵌入在运筹学、理论化学、计算机科学等许多领域的算法设计和分析方面是一个重要的要素。本项目主要研究图的度量空间在l1-空间中的等距离嵌入和扭曲嵌入的相关问题: 一探寻两个非二部的l1-图通过粘贴一条边后所得新图仍是l1-图的条件; 研究图G的线图L(G)的l1-嵌入性, 找出G与L(G)都是l1-嵌入的图; 二研究用禁止等距离子图来刻画l1-图的结构; 三研究圆柱面上的四边形镶嵌图的l1-嵌入性; 并研究圆柱面(莫比乌斯带)上的四(或六)边形镶嵌图的l1-嵌入的扭曲度; 四研究曲面图的共振图的超立方体嵌入及median性。该项目将图论与分析学, 几何学, 拓扑学, 代数学等很好的结合起来。本项目将进一步丰富和发展图的l1-嵌入的理论, 相关离散度量空间l1-嵌入的结果有助于分析学中的度量空间嵌入方面的研究。

人们通常将考虑的对象嵌入到理论较成熟的基本度量空间中，然后利用基本度量空间的特殊结构性质来获得更有效的算法。因此度量空间的嵌入在运筹学、理论化学、计算机科学等许多领域的算法设计和分析方面是一个重要的要素。本项目主要研究图的度量空间在l1-空间中的等距离嵌入和扭曲嵌入的相关问题。.主要研究内容及结果：.1.研究发现两个l1-图做门合并运算后仍然是l1-嵌入的。.2.研究了两个非二部l1-图(完全图、鸡尾酒会图和半立方图)两两粘边后所得新图的l1-嵌入性，发现两个完全图粘边后所得新图仍是l1-的，其他都是在平凡的情况下才是l1-嵌入的。.3. 研究发现树与单圈图及其线图都是l1-嵌入的。任何一棵超树都是l1-嵌入的，且n个顶点m条边的超树可以2倍嵌入到超立方体Q_{n+m-1}中。任何一个单圈超图都是l1-嵌入的。研究了双圈图以及它们的线图的l1-嵌入性, 得到“哑铃型”双圈图及其线图都是l1-嵌入的，“θ”型双圈图及其线图是l1-嵌入的当且仅当两个圈的交恰是一条边。.4. 研究了开口纳米管的边Wiener指标和边超Wiener指标的计算，用管长度和管粗度给出了它们的精确表达式。.5. 给出了对给定等距字符f，广义卢卡斯Q_n(f)超立方体能够等距离嵌入超立方体Q_n的充分必要条件。.6. 研究发现只有平凡的两类柱面四边形堆砌图是l1-嵌入的，其他都不是。证明了当4-边形上只有两个相邻3度点时，单一4-边形环己烷类图是l1-嵌入的，其他的都不是。.7.研究发现具有奇面的cata型平面图的共振图是median的，部分解决了Niko Tratnik和Ye（2017）的猜想。.8.还研究了距离谱半径、离心连通指标等，刻画了达到极值的图类。.本项目累计完成论文21篇，其中公开发表SCI检索论文10篇，中文核心4篇，接收待发表2篇，出版专著1部。.培养了8名硕士，其中5名已经毕业。.四年来，项目组参加了兰州大学、南开大学、华东理工大学、安徽大学、俄罗斯乌拉尔大学的图论研讨会以及中国工业与应用数学学会图论组合及应用专委会学术年会、第十届全国组合数学与图论大会等会议。参加了山东大学开办的《极值组合》课程、青海师范大学举办的DraganStevanovic教授的《图的谱半径》课程学习等。邀请了多名国内著名图论学者来校访问指导或者做线上学术报告等。加强了与国内外专家学者的学习和交流。