Signed degree sequences and multigraphs

We give necessary and sufficient conditions for the existence of a signed r‐multigraph with a prescribed signed degree sequence. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 101–105, 2002     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

平衡子欧拉符号图及符号线图

符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$.     

A Characterization of the degree sequences of 2‐trees

A graph G is a 2‐tree if G = K₃, or G has a vertex v of degree 2, whose neighbors are adjacent, and G/ v is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and realizing degree sequences of 2‐trees. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008     

图的符号星控制数与因子

利用图的因子研究图的符号星控制数,简化了文献中已有的结果.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r, n) such that every n-term graphic sequence π = (d1, d2,..., dn) with term sum σ(π) = d1 + d2 +…+ dn ≥σ(Kr,r, n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. πr has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.     

Convexity of degree sequences

We explore the convexity of the set of vectors consisting of degree sequences of subgraphs of a given graph. Results of Katerinis and Fraisse, Hell and Kirkpatrick concerning vertex deleted f‐factors are generalized. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 147–156, 1999     

Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs

Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.     

Graph classes characterized both by forbidden subgraphs and degree sequences

Given a set of graphs, a graph G is ‐free if G does not contain any member of as an induced subgraph. We say that is a degree‐sequence‐forcing set if, for each graph G in the class of ‐free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree‐sequence‐forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008     

两类图的符号控制数

图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n-Cm和n·Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n-Cm和n·Cm的符号控制数.     

On diameter and inverse degree of a graph

The inverse degree r(G) of a finite graph G=(V,E) is defined as , where is the degree of vertex v. We establish inequalities concerning the sum of the diameter and the inverse degree of a graph which for the most part are tight. We also find upper bounds on the diameter of a graph in terms of its inverse degree for several important classes of graphs. For these classes, our results improve bounds by Erd?s et al. (1988) [5], and by Dankelmann et al. (2008) [4].     

图的符号边控制数

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文确定了图F*n+1、H n和P*n的符号边控制数.     

A simple criterion on degree sequences of graphs

A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

符号圈拼接图的零度

令$\eta(\Gamma)$和$c(\Gamma)$是符号图$\Gamma$的零度和基本圈数. 一个符号圈拼接图是指每个块都是圈的连通符号图. 本文证明了对任意符号拼接图$\eta(\Gamma)\le c(\Gamma)+1$成立, 并且刻画了等号成立的极图, 推广了王登银等人(2022)在简单圈拼接图上的结果. 此外, 我们证明了任意的符号拼接图$\eta(\Gamma)\neq c(\Gamma)$, 给出了满足$\eta(\Gamma)=c(\Gamma)-1$的符号拼接图的一些性质并刻画处$\eta(\Gamma)=c(\Gamma)-1$的二部符号拼接图.     

图的k符号边控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)^/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)^/(G)的若干新下限,并确定了路和圈的k符号边控制数.     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .     

Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.