首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 500 毫秒
1.
2.
3.
4.
5.
6.
Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph G: its edge forwarding index π(G), arc forwarding index , undirected optical index , and directed optical index .In the paper we address two long-standing open problems: whether the equality holds for all graphs, and whether indices π(G) and are hard to compute. For the first problem, we give an example of a family of planar graphs {Gk} such that . For the second problem, we show that determining either π(G) or is NP-hard.  相似文献   

7.
8.
9.
Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.  相似文献   

10.
11.
12.
13.
14.
15.
16.
17.
Bc(G) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge as follows:
  相似文献   

18.
19.
20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号