原文

，卷:15(3)

• 查看PDF
• 下载

总感伤边半整块图

*通信:

Venkanagouda M Goudar，印度卡纳塔克邦图姆库尔斯里悉达多理工学院数学系，电话:9448579479;电子邮件: (电子邮件保护)

摘要

本文引入了树的总边半整块图的概念。我们得到了这个图的一些性质。我们研究了总边半全块图总是非平面的，并交叉1号、欧拉和哈密顿的图的刻画。

关键字

块图;边半整图;内顶点数;线形图

简介

设G (p,q)是顶点集V=p边集E=q的连通图。如果e=uv在e (G)中，那么顶点u和v是相邻的。对于图论表示法，我们遵循[1，2］．

在[3.Venkanagouda等引入了图值函数，树的pathos边缘半完整块图t。在[中引入了图G的块图B (G)2］．进一步研究了树的路径图P (T)， [3.］．

下面的定理将在续集中用到。

定理1 [6］．如果G是一个(p, q)图，其顶点的阶为d_我那么L (G)有q个顶点和qL条边

定理2 [6］．当且仅当G是平面的且1或2成立时，图G的线图L (G)的交叉数为1:

1.最大度数d (G)为4，且存在唯一的4度非切顶点。

2.最大度数d (G)为5，每一个4度的顶点都是一个切顶点，在任何块中都有一个唯一的5度顶点并且最多有3条边。

定理3 [2］．连通图G与其线图同构的当且仅当它是一个循环[4]。

定理4 [6］．一个图的线图L (G)是平面的当且仅当G是平面的，Δ≤4，且G的顶点v的度数v=4，则v为切顶点。

定理5 [1］．一个图是平面的当且仅当它没有与K同胚的子图₅或者K_{3, 3}．

定理六[9］．对于任意平面图G，边半整块图E_b(G)顶点的度数为d_我有(q+r+b)个顶点和

边，r是区域的数量，b是块的数量，q_ja块b中的边数_jb_k为切割顶点C的块度_k和问_r等于区域r上的边数₁．

定理7 [3.］．对于任意平面图G，顶点为d次的半整块图PEb (G)_我有(2q+k+1)个顶点边，r是区域的数量，b是块的数量，q_j边的数量在a块b中_jb_k为切顶点C的块度_k和问_r是区域r中的边数₁．

定理8 [1］．连通图G是欧拉的当且仅当G中的每个顶点都是偶次[5］．

定理9 [2］．一个非平凡图是二部的当且仅当它的所有循环都是偶的。

定理10 [3.］．对于任意树T，其边为半整块图PE_b(T)是平面的当且仅当T是星图K_{1, n}， n≥3。

总感伤边半整块图

在本节中，我们定义了树的总感伤边半完整块图。

定义2.1树T的总边半整块图，用T表示_体育(T)是顶点集是T的两个顶点T的边、块、区域和路径的集合的图_体育(T)相邻的如果都是相邻的边缘(T)或两块相邻的T或一块和其他优势e (T)和e谎言,或一个地区和其他优势e (T)和边缘e位于该地区或一个是T的感伤的道路和其他优势e T e位于路径或两者都是路径的路径p_我和p_jT和p的_我和p_j有一个共同的切割顶点。在图1，表示图G及其总感伤边半全块图[6］．

我们从以下直接结果开始。

备注1。对于任意树T，

备注2。对于任意图G, Tpe (G)=PE_b(t) u p (t)

备注3。对于任意边e_我在T中，边阶为n，顶点e '_我对应于e_我在T_体育(T)总是n+1。

结果

定理11。设T为树，总边为半整块图T_体育(T)总是不可分离的。

证明。假设T是一棵树，让e_我为了所有的i?T是T的边。在树T中，每条边都是一个块。让b₁= e₁b₂= e₂．b_米= e_米是方块r₁是T和p中唯一的区域₁p₂．p_k根据L (T)的定义，顶点e₁e₂．e_米L (T)的子图构成无切顶点的子图。同样在T中_体育(T)由区域形成的顶点叫做区域顶点它与e相邻_我对于所有i=1,2。M，来形成一个不可分离的图。因为有m块积木，每块是K₂，我们有每个b_我与e相邻_我对于所有的我。

进一步T包含一些悬垂的感伤点，这些感伤点对应于顶点p_我每一个p_我只与一个顶点e相邻吗_j这样，e_j变成一个切割顶点。同样在树中，至少有两条路径总是与T相邻_体育(T)是不可分离的[7］．

定理12。如果T (p, q)是一个连通图，其顶点的阶为d_我如果边e所对应的块数_我属于T的是b_我，则总感伤边半整块图T_体育(T)有2q+k+1个顶点边，其中q_j为每个块b中的边数_jbk为切顶点c的闭塞度_k．

证明。备注1:因此，T中的顶点数_体育(T) = PE的顶点数_b(T).根据定理7,V[PE_b(T)) = 2 q + k + 1。

进一步由Remark 2得到T中的边数_体育(T)与PE中的边数相同_b(T)和边数P(T)

根据定理7,PE中的边数_b(T)是．同样，路径图P(T)中的边数为这就是边的数量

定理13。对于任意树T T_体育(T)为非完全图。

证明。根据T的定义_体育(T)，区域与块之间没有邻接关系。在T_体育(T)区域顶点与块顶点之间无边。因此T_体育(T)为非完全图。

定理14。对于任意树T，总边是半完整的块图T_体育(T)不是二部图。

证明。在非路径的树中，至少包含一个顶点v (T)，使v的次≥3。设e1 e2 e3是与v有关的边根据T的定义_体育(T)，与v相交的边形成循环C_3.在T_体育(T).由定理9,T_体育(T)不是二部图。

定理15。对于任意树T T_体育(T) ?体育_b(T)当且仅当T是路径。

证明。设T是一条路径。根据定义，T_体育(T)、PE_b(T)有相同数量的顶点。因为T是一条路径，而路径的pathos图没有边，所以根据定义，T_体育(T)和PE_bT是同构的。

反过来假设T_体育(T) ?体育_b(T) T是非平凡连通树。现在我们证明T是一条路径。我们假设T至少有一个顶点v，使得v的次≥3。由注释2,T中的边数_体育(T)为边数PE之和_b(T)和P (T)中的边数，因此PE中的边数_b(T)小于T中的边数_体育(T)_体育(T) ?体育_b(T)，矛盾。因此，T是一条路径。

定理16。对于任意树T，总边为半完整块图T_体育(T)总是非平面的。

证明。设T是一个连通树，是一个* K_{1, n}， n≤3。根据定理10,PE_bT是平面的。让e₁= b₁e₂= b₂，和e_3.= b_3.这些边也是块r₁是区域和p₁p₂是T的悲怆之路_体育(T)顶点e₁e₂e_3.和r₁形成一个完全图K₄．块顶点为b₁b₂b_3.形成一个完全图K_3.和p之间的边₁和p₂必须穿过已经画好的边，因此T_体育(T)是非平面的。

如果T = K_{1, n}， n≥4，根据定理10,PE_b(T)是非平面的，因此T_体育(T)是非平面的。

定理17。对于任意树T，总边是半完整的块图T_体育当且仅当T = K时(T)有过1号叉_1、3．

证明。假设T_体育(T)有一个十字路口，显然是T_体育(T)是非平面的。根据定理16，我们有T=K_{1, n}， n≥4。假设T=K_{1, n}为n = 4。根据L (T)的定义，L (K_1、4) = K₄．因为T的每条边都只在一个区域r上₁所以在T中_体育(T) K的所有顶点₄与区域顶点r相邻吗₁形成K5，显然它有1号交叉。在树T中，每条边都是一个块，所有块都是b₁b₂b_3.和b₄彼此相邻。根据T的定义_体育(T)，四个块顶点构成K₄作为子图，显然是内顶点b_我它与e相邻吗_我对应于T中的e 'i_体育(T)构成另一个交叉数。因此T_体育(T)至少有两个交叉数，矛盾[9，10］．

反过来证明，证明K₅是一个子图，它的交叉号是1。根据线形图的定义，L (K_1、3) = K_3.所有的边都只在一个区域上。在T_体育(T)，区域顶点r₁是否与所有顶点相邻对应于T的边它形成了一个完整的图K₄．每条边是一个块，所有的块组成K_3.作为子图。同样，相邻顶点p1是e₁和e₂p₂与e相邻_3.这些悲怆的顶点彼此相邻形成了一号交叉点。因此，Cr [T_体育(T)) = 1。

定理18。对于任意树T，总边是半整块图T_体育(T)是欧拉式的当且仅当T是星K_{1、4 n + 2}对于n≥1。

证明。假设T_体育T是欧拉式。我们考虑以下几种情况。

案例1。假设T是任意非星形树T，我们有下面的子情况。

子案例1.1。令u v ?T使度(u)=3度(v)=2。让e₁e₂e_3.是与u和e相关的边_3.e₄是与v相关联的边，显然是边e的边度₁是4。由备注3，对应顶点在T_体育(T)的次数是5，是奇数。根据定理8,T_体育(T)是非欧拉的，一个矛盾。

子情况1.2。假设T包含一条边，每条边的边度都是偶数，只有当T的边总数为奇数时才有可能。根据TPe (T)的定义，度(ri)变为奇数。根据定理8,TPe (T)是非欧拉的，这是一个矛盾。

例2。假设T=K1, p其中p≠4n+2。我们有下面的子情形。

子案例2.1。我们假设T=K₁， 3n+1 n=1.2。k，通过情形1,k的每条边₁，_3.有4次边，根据定理2，对应的顶点在T_体育(T)边度为奇数，也就是奇数。根据定理8,T_体育(T)是非欧拉的，一个矛盾。

子案例2.2。假设T=K_1、4．在情形1中，每条边e_我在T中有边度奇数。由注3,T中对应顶点e1_体育(T)有偶数度。区域顶点r '_我是否与所有四个顶点v相邻¹_我， i= 1,2,3,4，形成一个顶点都是偶次的图。在T中，有两条pathos p1和p2路径，每个pathos包含两条边。在T_体育(T)，两个顶点相邻形成图与两个p₁和p₂有奇数度。根据定理8,T_体育(T)是非欧拉的，一个矛盾。

反过来假设T=K_{1、4 p + 2}对于p = 1, 2。n.在树T中，每条边e_我有奇数度，根据注释3，顶点对应于e_我关于T in T_体育(T)变成偶次。如果T的总边数为偶数，则区域顶点为T_体育(T)变成偶次。同样，每条边都是块e_我= b_我对于所有i，每个block b_我与剩余块和e相邻_我与b相邻_我形成偶数度。最后，与偶数条边相邻且每个pathos与剩余2n条路径相邻的pathos顶点。然后在T中_体育(T)，每个顶点都是偶次的。因此T_体育T是欧拉式。

定理19。对于任意树T T_体育T是哈密顿量。

证明。假设T是一棵树。我们考虑以下几种情况。

案例1。设T是星K_{1, n}， n对于顶点u是奇数₁,你₂u_3.．．．．u_nu_{n + k}这样u的度₁=n，令b₁b₂……b_米为块数，ri为区域数，路径数为T只包含一个区域。根据T的定义_体育(T), V (T_体育(T)) = {e₁e₂e_3.. . . . . .e_nb₁b₂， . . . . .b_{n - 1}｝那么存在一个包含T的顶点的循环_体育(T)作为p₁p₂p_3.p,……_ke₅e_kb_kb_{k - 1}……b₁e₁e_3.r.e…₂p₁它包含T的所有顶点_体育(T)。因此它是一个哈密顿循环。

例2。让T = K_{1, n}n>2，是偶数。那么悲怆的路径数是Let V [T]_体育(T)) = {e₁e₂. . . .e_nb₁b₂……b_{n - 1}} U {p₁p₂. . . . . .} U r₁则存在一个包含T的顶点的循环_体育(T)作为p₁p₂e,……_kb_kb_{k - 1}……b₁e₁r。e₂p₁是一个汉密尔顿循环。因此T_体育T是哈密顿量。

例3。假设T既不是路径也不是星号，那么T包含至少两个度为>2的顶点。让e₁e₂. . . . .e_n是T的边，使得e₁= b₁e₂= b₂. . . . .e_n= b_n做积木。然后V [T]_体育(T)) = {e₁e₂……e_nb₁b₂. . . .b_n｝p {₁p₂. . . . .p_我｝r₁其中T有p_我i > 1的所有顶点，每个顶点都与T的边相邻，其中对应的顶点位于T的边上，则存在一个包含T的所有顶点的循环C_体育(T)为p1, e₁b₁e₂p₂e_3.. . . . . . . . .r₁在p₁．因此T_体育T是哈密顿量。显然T_体育T是哈密顿量。

例4。假设T是一条路径。让你₁,你₂u_3.. . . . .u_n做一条路。顶点集合V [T]_体育(T)) = {e₁e₂. . . .e_nb₁b₂……b_{n - 1}} U {p₁} U r₁．显然存在一个包含T的顶点的循环_体育(T)作为p₁e,……_kb_kb_{k - 1}……b₁e₁r。e₂p₁是一个汉密尔顿循环。因此T_体育T是哈密顿量。

结论

本文定义了树的总边半全块图。我们描述了总边半整块图是平面的、哈密顿的且有交叉数为1的图。

参考文献

1. Harary F.纽约年鉴。中国科学院学报。1977;175:198。
2. 图论。Addison-Wesley Reading Mass, 1969;72:107。
3. Jagadeesh N,Venkanagouda M Goudar。Pathos边半整块图。数学学报。2015;6:395-402。
4. Kulli虚拟现实。关于最小非外平面图，印度国家科学院学报，1975;41。
5. Kulli VR,Akka DG。数学学报。1980;14(4):585- 888。
6. 交换图的一些性质。图表和应用程序。学术出版社，纽约，1962。
7. 史丹顿RG，考文DD，罗伟文。路易斯安那州组合学会议论文集。图论与计算。1970;页:112。
8. Goudar VM。在Pathos顶点上，树的半整图。清华大学学报(自然科学版)，2012;
9. Goudar VM,Jagadeesh N.边缘半全块图。中国计算机科学，2014;39(4):344 - 344。
10. MaralabhaviYB, Muddebihal,Goudar VM。在树的帕索斯边的半整图上。在远东。应用程序数学。2007;27:85-91。