两类图的L(2.1)-标号数

图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数.     

平面图的(3,1)~*-可选择性

若对图G的任何一个满足|L(v)|=k的列表配置L,存在G的一个L-染色c使G的每个顶点v至多有d个邻点和v染相同的颜色,则称图G是(k,d)~*-可选的.本文证明了:(1)若G是i-圈和j-圈(i,j∈{3,4})不相交的平面图,则G是(3,1)~*-可选的.(2)不含6圈和相交3-圈的平面图是(3,1)~*-可选的.     

重图的均匀边染色

图G的一个边染色称为是均匀的,如果对G的每个顶点v,与v关联的染任意两种颜色的边数至多相差一,我们给出了重图均匀边染色的一个充分条件。     

平面图4-可选的一个局部条件

给定图G的一个k-色列表L,若存在G的一个正常染色c且满足c(v)∈L(v),则称G是L-列表可染的.若对任意k-色列表L, G都是L-列表可染的,则称G是k-可选的.本文给出平面图4-可选的一个局部条件,即若平面图G的每个点不同时与3-、4-、5-和6-圈相关联,则G是4-可选的.     

不含相交6-圈的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色·一个图G称为单射κ-可选择的,如果对于顶点V(G)的任何一个大小为κ的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v)使得G为单射κ-可选择的最小κ,称为G的单射可选择数,记作X_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数X(∑)≥0的曲面∑的一个图,证明了若Δ≥7,g≥6,且不含有相交6-圈,则x_i~l(G)≤Δ+2.     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

具有较小直径的三类图的对极色数

对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

图的Hyper-Wiener指数的综述(英文)

设G是一个图.G的顶点u和v的距离是u和v之间最短路的长度.Wiener指数是G中所有无序顶点对之间距离之和,而Hyper-Wiener指数定义为WW(G)=?∑u,v∈V(G)d(u,v)+?∑u,v∈V(G)d2(u,v),式中的和取遍G的所有顶点对.本文总结了图的Hyper-Wiener指数的最近结论.     

完全多部图K_(1*r,3*(k-2))的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

一个六点九边图的图设计

令Kv表示v个顶点的完全图,G是一个不含孤立点的简单连通图.一个v阶的G-设计是将Kv划分成互不相交的子图,使得每个子图都和G同构,记为G-GD(v).研究六点九边图G11的图设计存在性问题.利用标准的递推构造并结合必要的直接构造,证明除去G11-GD(9)不存在以及G11-GD(18)的存在性未知外,G11-GD(v...     

Coloring of Plane Graphs with Unique Maximal Colors on Faces

The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven.     

Aglianò-Montagna type decomposition of linear pseudo hoops and its applications

We decompose every linear pseudo hoop as an Aglianò-Montagna type of ordinal sum of linear Wajsberg pseudo hoops which are either negative cones of linear ?-groups or intervals in linear unital ?-groups with strong unit. We apply the decomposition to present a new proof that every linear pseudo BL-algebra and consequently every representable pseudo BL-algebra is good. Moreover, we show that every maximal filter and every value of a linear pseudo hoop is normal, and every σ-complete linear pseudo hoop is commutative.     

On the two-dimensional orthogonal drawing of series-parallel graphs

It has been known that every planar 4-graph has a 2-bend 2-D orthogonal drawing, with the only exception being the octahedron, every planar 3-graph has a 1-bend 2-D orthogonal drawing with the only exception being K₄, and every outerplanar 3-graph with no triangles has a 0-bend 2-D orthogonal drawing. We show in this paper that every series-parallel 4-graph has a 1-bend 2-D orthogonal drawing.     

Products of idempotent matrices over integral domains

We say that a ring R has the idempotent matrices property if every square singular matrix over R is a product of idempotent matrices. It is known that every field, and more generally, every Euclidean domain has the idempotent matrices property. In this paper we show that not every integral domain has the idempotent matrices property and that if a projective free ring has the idempotent matrices property then it must be a Bezout domain. We also show that a principal ideal domain has the idempotent matrices property if and only if every fraction a/b with b≠0 has a finite continued fraction expansion. New proofs are also provided for the results that every field and every Euclidean domain have the idempotent matrices property.     

Triple Systems are Eulerian

An Euler tour of a hypergraph (also called a rank‐2 universal cycle or 1‐overlap cycle in the context of designs) is a closed walk that traverses every edge exactly once. In this paper, using a graph‐theoretic approach, we prove that every triple system with at least two triples is eulerian, that is, it admits an Euler tour. Horan and Hurlbert have previously shown that for every admissible order >3, there exists a Steiner triple system with an Euler tour, while Dewar and Stevens have proved that every cyclic Steiner triple system of order >3 and every cyclic twofold triple system admits an Euler tour.     

Projective algebras and primitive subquasivarieties in varieties with factor congruences

We prove that in the varieties where every compact congruence is a factor congruence and every nontrivial algebra contains a minimal subalgebra, a finitely presented algebra is projective if and only if it has every minimal algebra as its homomorphic image. Using this criterion of projectivity, we describe the primitive subquasivarieties of discriminator varieties that have a finite minimal algebra embedded in every nontrivial algebra from this variety. In particular, we describe the primitive quasivarieties of discriminator varieties of monadic Heyting algebras, Heyting algebras with regular involution, Heyting algebras with a dual pseudocomplement, and double-Heyting algebras.     

Weakly quasi-o-minimal models

We introduce the notion of a weakly quasi-o-minimal model and prove that such models lack the independence property. We show that every weakly quasi-o-minimal ordered group is Abelian, every divisible Archimedean weakly quasi-o-minimal ordered group is weakly o-minimal, and every weakly o-minimal quasi-o-minimal ordered group is o-minimal. We also prove that every weakly quasi-o-minimal Archimedean ordered ring with nonzero multiplication is a real closed field that is embeddable into the field of reals.     

Orienting planar graphs

It is shown that every maximal planar graph (triangulation) can be contracted at an arbitrary point (by identifying it with an adjacent point) so that triangularity is preserved. This is used as a lemma to prove that every triangulation can be (a) oriented so that with three exceptions every point has indegree three, the exceptions having indegrees 0, 1 and 2, and (b) decomposed into three edge-disjoint trees of equal order. The lemma also provides an elementary proof of a theorem of Wagner that every triangulation can be represented by a straight-line drawing.     

Terminable and interminable paths and trails in infinite graphs

The paper is concerned with certain kinds of random processes in infinite graphs. A finite trail of a graph which cannot be continued from either end is called terminated, and a finite trail is called terminable of it is a segment of a finite terminated trail; analogously for 1 - ∞ trails, finite paths, and 1 - ∞ paths.For k = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have node-connectivity k and in which no finite path and no 1 - ∞ path is terminable, and also such graphs in which every finite path and every 1 - ∞ path is terminable. In any graph with infinite node-connectivity every node of valency N₀ is the end-node of terminated 1 - ∞ paths. There exist graphs with node-connectivity N₀ in which every 1 - ∞ path is terminable. For λ = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have edge-connectivity λ and in which no finite trail and no 1 - ∞ trail is terminable, and also such graphs in which every finite trail and every 1 - ∞ trail is terminable. In contrast to the situation for 1 - ∞ paths, every connected infinite graph in which every 1 - ∞ trail is terminable contains at least one node of odd edge-degree and if in addition every finite trail is terminable, then there are at least two nodes of odd edge-degree.     

Twisted cohomology pairings of knots I; diagrammatic computation

We provide a diagrammatic computation for the bilinear form, which is defined as the pairing between the (relative) cup products with every local coefficients and every integral homology 2-class of every link in the 3-sphere. As a corollary, we construct bilinear forms on the twisted Alexander modules of links.