字典积图的任意可分性

给定n个顶点的图G,对于满足∑_(i=1)^(k)n_(i)=n的任意一个正整数序列(n_(1),n_(2),…,n_(k)),如果都存在顶点集V(G)的划分(V_(1),V_(2),…,V_(k)),满足Vi导出的子图G[V_(i)]是连通的,并且|V_(i)|=n_(i),其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H,其顶点集为V(G)×V(H),(g,h)(g,h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为(T)的顶点属于顶点集V(P),则字典积图T○Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G○H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G○G是任意可分图;如果G是哈密顿图且H是一个图,则G○H是任意可分图.

T-型树T(1,l,m)可由其谱唯一决定

一棵树称为T-型树,如果其恰有一个最大度为3的顶点.令T(l1,l2,l3)表示唯一的一棵T-型树,使得其3-度顶点到每个1-度顶点的距离分别为l1,l2,l3.本文证明T(1,l,m)(l,m≥1)可由其相邻谱唯一决定.

有线电视数字光纤分配网设计

有线电视运营商如何以有限的资金建设既符合技术规范又符合业务发展需要的光纤网络,已成为亟待解决的问题。本文主要对光纤分配网中最常用的星型和树星型两种结构进行对比分析,以寻求适合有线电视运营商的光纤分配网结构。

给定度序列图的覆盖成本和反向覆盖成本的研究

具有n个顶点且度序列为(m,2,…,2,1,…,1)(1的重数为m)的连通图不止一个(这些图均为树),而每个树对应唯一一个段序列(l_(1),l_(2),…,l_(m)).通过对任意一树移动最长段的悬挂点到最短段悬挂点的方式得到另一树,比较前后两树的覆盖成本和反向覆盖成本,给出了具有最小覆盖成本和反向覆盖成本的极树,并且进一步给出了取得最小覆盖成本和反向覆盖成本的顶点.