含有割点的图的最小特征值

Let ψ be a certain set of graphs.A graph is called a minimizing graph in the set ψ if its least eigenvalue attains the minimum among all graphs in ψ.In this paper,we determine the unique minimizing graph in ψn,where ψn denotes the set of connected graphs of order n with cut vertices.     

图的3限制性边割

3限制性边割将连通图分离成不连通图，使其各连通分支含有至少3个顶点．含3限制性边割的图在本文中得到刻划．     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

The Least Eigenvalue of Graphs with Cut Edges

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut edges.     

On the Crossing Numbers of Products of Stars and Graphs of Order Five

 There are several known exact results on the crossing numbers of Cartesian products of paths or cycles with “small” graphs. In this paper we extend these results to the Cartesian products of two specific 5-vertex graphs with the star K _{1, n} . In addition, we give the crossing number of the graph obtained by adding two edges to the graph K _{1,4, n} in such a way that these new edges join a vertex of degree n+1 of the graph K _{1,4, n} with two its vertices of the same degree. Received: December 8, 1997 Final version received: August 14, 1998     

Improved Upper Bounds on the Domination Number of Graphs With Minimum Degree at Least Five

An algorithmic upper bound on the domination number \(\gamma \) of graphs in terms of the order n and the minimum degree \(\delta \) is proved. It is demonstrated that the bound improves best previous bounds for any \(5\le \delta \le 50\). In particular, for \(\delta =5\), Xing et al. (Graphs Comb. 22:127–143, 2006) proved that \(\gamma \le 5n/14 < 0.3572 n\). This bound is improved to 0.3440 n. For \(\delta =6\), Clark et al. (Congr. Numer. 132:99–123, 1998) established \(\gamma <0.3377 n\), while Biró et al. (Bull. Inst. Comb. Appl. 64:73–83, 2012) recently improved it to \(\gamma <0.3340 n\). Here the bound is further improved to \(\gamma < 0.3159n\). For \(\delta =7\), the best earlier bound 0.3088n is improved to \(\gamma < 0.2927n\).     

划分围长至少为6 的平面图为有界大小的分支

图$G$的$(\mathcal{O}_{k_1}, \mathcal{O}_{k_2})$-划分是将$V(G)$划分成两个非空子集$V_{1}$和$V_{2}$, 使得$G[V_{1}]$和$G[V_{2}]$分别是分支的阶数至多$k_1$和$k_2$的图.在本文中,我们考虑了有围长限制的平面图的点集划分问题,使得每个部分导出一个具有有界大小分支的图.我们证明了每一个围长至少为6并且$i$-圈不与$j$-圈相交的平面图允许$(\mathcal{O}_{2}$, $\mathcal{O}_{3})$-划分,其中$i\in\{6,7,8\}$和$j\in\{6,7,8,9\}$.     

周长为4不含3圈的m限制边连通图

m限制边割是连通图的一个边割,它将此图分离成阶不小于m的连通分支刻画了周长为4,不含3圈的m限制边割的图类.     

关于图符号的边控制 (英)

设γ's(G)和γ'ι(G)分别表示图G的符号边和局部符号边控制数,本文主要证明了:对任何n阶图G(n≥4),均有γ's(G)≤[11/6n-1]和γ'ι(G)≤2n-4成立,并提出了若干问题和猜想．     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

最小次数至少为4的超欧拉图

设Ｇ是２－边－连通的ｎ阶图。假设对任何的的最小边割集Ｅ等于包含于Ｅ（Ｇ）且│Ｅ│≤３,Ｇ－Ｅ的每个分支的阶至少为ｎ／５,则或者Ｇ是一个超欧拉图或者Ｇ有５个互不相交的阶数为ｎ／５连通分支,当这５个分支都收缩时,Ｇ收缩为Ｋ２,３,这个结果推广了蔡小涛,Ｐ．Ａ．Ｃａｔｌｉｎ,Ｆ．Ｊａｅｇｅｒ和Ｈ．Ｊ．Ｌａｉ等人关于超欧拉图的结果。     

On Edge Semi-Isomorphisms and Semi-Dualities of Graphs

Let G₁ and G₂ be undirected graphs, and ?₁(G ₁) and ?₂(G ₂) be families of edge sets of G₁ and G₂, respectively. An (?₁,?₂)-semi-isomorphism ofG ₁ ontoG ₂ is an edge bijection between G₁ and G₂ that induces an injection from ?₁(G ₁) to ?₂(G ₂). This concept generalizes a well known concept of a circuit isomorphism of graphs due to H. Whitney. If has a “dual nature” with respect to ?₂(G ₂) then the concept of (?₁,?₂)-semi-isomorphism of graphs turns into a concept of a (?₁,?₂)-semi-duality of graphs. This gives a natural generalization of the circuit duality of graphs due to H. Whitney. In this paper we investigate (?₁,?₂)-semi-isomorphisms and (?₁,?₂)-semi-dualities of graphs for various families ?₁(G ₁) and ?₂(G ₂). In particular, we consider families of circuits and cocircuits of graphs from this point of view, and obtain some strengthenings of Whitney’s 2-isomorphism theorem and Whitney’s planarity criterion for 3-connected graphs.     

Characterizing Graphs with Crossing Number at Least 2

Our main result includes the following, slightly surprising, fact: a 4‐connected nonplanar graph G has crossing number at least 2 if and only if, for every pair of edges having no common incident vertex, there are vertex‐disjoint cycles in G with one containing e and the other containing f.     

Chromatic Index Critical Graphs of Even Order with Five Major Vertices

We prove that there does not exist any chromatic index critical graph of even order with exactly five vertices of maximum degree. This extends an earlier result of Chetwynd and Hilton who proved the same with five replaced by four or three.     

Gallai's Conjecture For Graphs of Girth at Least Four

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path‐decomposition of G having at most paths. In this article, we show that for any simple graph G having girth , there is a path‐decomposition of G having at most paths, where is the number of vertices of odd degree in G and is the number of nonisolated vertices of even degree in G.     

关于图的一般邻点可区别边染色

给出了轮图W_n、扇图F_n、风车图K_2~t、图D_(m,4)、图D_(m,n)、齿轮图W_n的一般邻点可区别色指标.     

关于图的符号边全控制数

Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.     

关于图的符号边全控制数

引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.     

最小度不小于3的图的圈长问题

Bondy和Vince曾证明最小度不小于3的图包含两个长度相差为1或者2的圈,这个结果回答了ErdSs提出的问题．Haggkvist和scott证明了除肠外,所有的3-正则图都包含两个长度相差2的圈．通过不同的方法,我们得到了下面的结论：除了每个端块都是硒的图外,所有最小度不小于3的图都包含两个长度相差2的圈．     

(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface

A graph is ‐colorable if its vertex set can be partitioned into r sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least g are ‐colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if d₂(5, 1) is finite. We answer this question in the affirmative with ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.