通往图的双圈覆盖猜想的新途径

本文提出了一些新的方法以接近图的用圈二重覆盖边的猜想,通称图的双圈覆盖猜想。因２０余年尚未解决而在图论中著名。从中,也提出了一些新的猜想。并论述了它们之间,以及它们与图的驿圈盖猜想之间的关系。     

无交双圈图的邻接矩阵的奇异性

一个无交双圈图G的邻接矩阵是奇异的当且仅当G含有4m(m∈N)阶圈，或G含有完美匹配和G—V(c1)，G-V(c2)均含有完美匹配且G中含有4κ1 3与4e1 1(κ1，e1∈N)阶圈，或G、G-V(c1)、G—V(c2)、G—V(c1)-V(c2)均无完美匹配．无交双圈图的邻接矩阵的最大行列式值为16。     

平衡二部图的四圈覆盖

对任意的正整数ｋ,如果每部２ｋ个点的平衡二部图Ｇ＝（ｖ１,ｖ２;Ｅ）的最小度大于等于４ｋ／３,那么Ｇ恰好被ｋ个相互独立的四圈覆盖。     

恰有k个悬挂点的n阶双圈和三圈图的拟拉普拉斯谱半径

设k,n为两个确定的正整数.本文得到了当1≤k≤n-7时恰有k个悬挂点的n阶连通三圈图的最大拟拉普拉斯谱半径的唯一极图,也得到了当1≤k≤n-5时恰有k个悬挂点的n阶连通双圈图的最大拟拉普拉斯谱半径的唯一极图.     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

关于｛P2,Ci│i≥3｝—覆盖图

设Ｇ是一个图,若对于Ｇ的任意一边Ｇ都有｛Ｐ２,Ｃｉ│ｉ≥３｝－因子含有这条边,则称Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图。本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图的充要条件为任给Ｓ包含于Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠ф有ｉ（Ｇ－Ｓ）≤│Ｓ│－１成立。     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。     

双圈图的最大Estrada指数

令Bn^＋表示顶点个数为礼的双圈二部图的集合．考虑了召吉中图依Estrada指数从大到小的排序问题．利用二部图的Estrada指数和最大特征值之间的关系,当n≥8时,得到了Bn^＋中具有最大和次大Estrada指数的图．     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

关于3正则图的三匹配交猜想(Ⅱ)

Fan和Raspaud 1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配．本文证明了如下结果：若G是一个圈4-边连通的无桥3正则图，且存在G的一个完美匹配M1使得G—M1恰为4个奇圈的不交并，则存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=Φ。     

Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

On Orthogonal Double Covers of Graphs

A transformation which allows us to obtain an orthogonal double cover of a graph G from any permutation of the edge set of G is described. This transformation is used together with existence results for self-orthogonal latin squares, to give a simple proof of a conjecture of Chung and West.     

On the Toughness of Cycle Permutation Graphs

Motivated by the conjectures in [11], we introduce the maximal chains of a cycle permutation graph, and we use the properties of maximal chains to establish the upper bounds for the toughness of cycle permutation graphs. Our results confirm two conjectures in [11].     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

Cycle and cocycle coverings of graphs

In this article, we show that for any simple, bridgeless graph G on n vertices, there is a family ?? of at most n?1 cycles which cover the edges of G at least twice. A similar, dual result is also proven for cocycles namely: for any loopless graph G on n vertices and ε edges having cogirth g^*?3 and k(G) components, there is a family of at most ε?n+k(G) cocycles which cover the edges of G at least twice. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 270–284, 2010     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number

Let G =(V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function(SCDF) of G if ∑_(e∈E(C))f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ'_(sc)(G) = min{∑_(e∈E)f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ'_(sc)(G) = n.     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(C1，C2，…，Cn)，其中ci是图G中长为i的圈数．本文得到如下结果：设A∈_E(Kn,r)，|A|≤1，且n≤r≤min{n 6，2n-3)，则G=Kn,r，r-A是由它的圈长分布确定的．     

On Perfect Matching Coverings and Even Subgraph Coverings

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture.