关于图中离心率的一些极值问题
发布时间：2019-01-05 06:07
【摘要】：本文中所涉及的所有的图均为简单的无向连通图。连通图G的两个顶点u和v之间的距离dG(u,v)定义为u和v之间的最短路的长度,而u的离心率eccG(u)是指u到图G中其他所有点的最大距离。连通图G的中心集C(G)和边缘集P(G)分别由具有最小离心率和最大离心率的顶点组成的集合。着|C(G)| = |V(G) | - 2 ,称图G为几乎自中心图(almost self-centered graph,简记ASC 图)。若|P(G)| = |V(G)| -1,称图 G为几乎边缘图(almost-peripheral graph,简记 AP图)。本文分别研究几乎自中心图和几乎边缘图的极值问题。第一章简单介绍了本文中所涉及图的一些基本的概念、符号和相关的研究背景,并且给出了AS 图和AP图的相关定义。第二章给出阶为n的完全图、路、圈、以及直径为n -2 (n≥10)的树的3-ASC指标。同时证明了直径为2的图G的指标θ3(G)∈ {3,4}等极值结论。在第三章中我们研究几乎边缘图的一些构造问题,并给出任意图G的指标上界等极值问题。第四章对本论文进行了总结并列举了一些论文中还有待进一步解决的问题。
[Abstract]:All the graphs involved in this paper are simple undirected connected graphs. The distance between two vertices u and v of a connected graph dG (uv) is defined as the length of the shortest path between u and v, and the centrifuge eccG (u) of u is the maximum distance between u and all other points in graph G. The center set C (G) and edge set P (G) of connected graph G are composed of vertices with minimum centrifuge rate and maximum centrifuge rate respectively. By C (G) = V (G)-2, the graph G is almost self-centered (almost self-centered graph, ASC graph). If P (G) is V (G)-1, the graph G is almost edge graph (almost-peripheral graph, AP graph). In this paper, we study the extremum problem of almost self center graph and almost edge graph respectively. The first chapter briefly introduces some basic concepts, symbols and related research background of the graphs involved in this paper, and gives the relevant definitions of AS graphs and AP graphs. In chapter 2, we give the 3-ASC indices of complete graphs, paths, cycles and trees with n -2 diameter (n 鈮，
本文编号：2401381
[Abstract]:All the graphs involved in this paper are simple undirected connected graphs. The distance between two vertices u and v of a connected graph dG (uv) is defined as the length of the shortest path between u and v, and the centrifuge eccG (u) of u is the maximum distance between u and all other points in graph G. The center set C (G) and edge set P (G) of connected graph G are composed of vertices with minimum centrifuge rate and maximum centrifuge rate respectively. By C (G) = V (G)-2, the graph G is almost self-centered (almost self-centered graph, ASC graph). If P (G) is V (G)-1, the graph G is almost edge graph (almost-peripheral graph, AP graph). In this paper, we study the extremum problem of almost self center graph and almost edge graph respectively. The first chapter briefly introduces some basic concepts, symbols and related research background of the graphs involved in this paper, and gives the relevant definitions of AS graphs and AP graphs. In chapter 2, we give the 3-ASC indices of complete graphs, paths, cycles and trees with n -2 diameter (n 鈮，
本文编号：2401381
本文链接：https://www.wllwen.com/kejilunwen/yysx/2401381.html
