共查询到17条相似文献,搜索用时 46 毫秒
1.
对于图G(或者有向图D)内的任意两点u和υ,u-υ测地线是指在u和υ之间的最短路(或者从u到υ).I(u,υ)表示位于一条u-υ测地线上所有点的集合,对于S(U∣)V(G),I(S)表示所有I(u,υ)的并,这里u,υ∈S.图G(或者有向图D)的测地数g(G)(g(D))是使J(S)=V(G)(J(S)=V(D))的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-(G)=min{g(D):D是G的定向图);定义G的所有定向图中测地数的最大值为G的上测地数,即g+(G)=max{g(D):D是G的定向图).本文的主要目的是研究G V H 的上、下测地数,此外,文章给出了g(G)=g(G×P3)的一个充分必要条件. 相似文献
2.
3.
图G内的任意两点u和v, u-v测地线是指u和v之间的最短路. I(u,v)表示 位于u-v测地线上所有点的集合, 对于子集SÍV(G), I(S)表示所有I(u,v)的并, 这里u,vÎ S. 图 G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数. 对于有向图D, 类似地可定义g(D). 图G 的测地谱是G的所有定向图的测地数的集合, 记为S(G). G的下测地数g-(G)=minS(G), 上测地数g+(G)=maxS(G). 文中主要研究了连通图G的g(G), g-(G)和g+(G)之间的关系. 同时,还给出g(G)和g(G× K2)相等的充分必要条件, 从而推广了 Chartrand, Harary 和 Zhang 的相关结论. 相似文献
4.
5.
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results. 相似文献
6.
7.
8.
9.
早在上世纪五十年代,Zarankiewicz猜想完全2-部图Km,n(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数).目前这一猜想的正确只证明了当m≤6时成立.本文主要证明了若Zarankiewicz猜想对m=7成立,则完全3-部图K1,6,n的交叉数为9[n/2][n-1/2] 6[n/2]. 相似文献
10.
设Hn(n≥5)表示一个图:以1,2,...,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n.这篇文章证明了,Hn的色数等于它的选择数.结果被用于刻画最大度至多2的图的列表全色数. 相似文献
11.
For two vertices u and v of a graph G, the closed interval I[u, v] consists of u, v, and all vertices lying in some u–v geodesic of G, while for S V(G), the set I[S] is the union of all sets I[u, v] for u, v S. A set S of vertices of G for which I[S] = V(G) is a geodetic set for G, and the minimum cardinality of a geodetic set is the geodetic number g(G). A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in G is its extreme order ex(G). A graph G is an extreme geodesic graph if g(G) = ex(G), that is, if every vertex lies on a u–v geodesic for some pair u, v of extreme vertices. It is shown that every pair a, b of integers with 0 a b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r, d, and k 2, it is shown that there exists an extreme geodesic graph G of radius r, diameter d, and geodetic number k. Also, for integers n, d, and k with 2 d > n, 2 k > n, and n – d – k + 1 0, there exists a connected extreme geodesic graph G of order n, diameter d, and geodetic number k. We show that every graph of order n with geodetic number n – 1 is an extreme geodesic graph. On the other hand, for every pair k, n of integers with 2 k n – 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph. 相似文献
12.
WANG Xiu-mei 《数学季刊》2004,19(4)
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results. 相似文献
13.
The geodetic numbers of graphs and digraphs 总被引:1,自引:0,他引:1
Chang-hong LU~ 《中国科学A辑(英文版)》2007,50(8):1163-1172
For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang. 相似文献
14.
Tanaka Hiroyuki & Teragaito Masakazu 《数学研究通讯:英文版》2016,32(1):1-38
We introduce the triple crossing number,a variation of the crossing number,of a graph,which is the minimal number of crossing points in all drawings of the graph with only triple crossings.It is defined to be zero for planar graphs,and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings.In this paper,we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs. 相似文献
15.
16.
关于图的团符号控制数 总被引:2,自引:0,他引:2
引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想. 相似文献
17.
Ellen Gethner Leslie Hogben Bernard Lidický Florian Pfender Amanda Ruiz Michael Young 《Journal of Graph Theory》2017,84(4):552-565
The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing. 相似文献