Partitioning a Graph into Highly Connected Subgraphs

Given , a k‐proper partition of a graph G is a partition of such that each part P of induces a k‐connected subgraph of G. We prove that if G is a graph of order n such that , then G has a 2‐proper partition with at most parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if G is a graph of order n with minimum degree where , then G has a k‐proper partition into at most parts. This improves a result of Ferrara et al. ( Discrete Math 313 (2013), 760–764), and both the degree condition and the number of parts is best possible up to the constant c.     

Monte Carlo Algorithms for Identifying Densely Connected Subgraphs

The problem of finding densely connected subgraphs in a network has attracted a lot of recent interest. Such subgraphs are sometimes referred to as communities in social networks or molecular modules in protein networks. In this article, we propose two Monte Carlo optimization algorithms for identifying the densest subgraphs with a fixed size or with size in a given range. The new algorithms combine the idea of simulated annealing and efficient moves for the Markov chain, and both algorithms are shown to converge to the set of optimal states (densest subgraphs) with probability 1. When applied to a yeast protein interaction network and a stock market graph, the algorithms identify interesting new densely connected subgraphs. Supplementary materials for the article are available online.     

有限连通图上随机扩张森林和连通子图的边负相关性

设G为有限连通图．本文研究图G的子图空间G上的三类概率测度,它们分别刻画图的随机扩张树,随机扩张森林和随机连通子图．基于G上均匀扩张树的边负相关性,我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图．此外,我们还给出一定条件下图上均匀扩张森林的边负相关性．     

Forbidden Induced Subgraphs for Toughness

Let be a family of connected graphs. A graph G is said to be ‐free if G is H‐free for every graph H in . We study the relation between forbidden subgraphs in a connected graph G and the resulting toughness of G. In particular, we consider the problem of characterizing the graph families such that every large enough connected ‐free graph is t‐tough. In this article, we solve this problem for every real positive number t. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 191–202, 2013     

导出子图和周长的局部定理

设G是n阶2-连通图，3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L，若d（u）且如果dL（u，v）=2有（v）=min{，|M3（u）|/2}这里M3（u）={v|dc（u,v）≤3}，则G包含长至少为c的圈．     

Forbidden Induced Subgraphs for Perfect Matchings

Let ${\mathcal{F}}$ be a family of connected graphs. A graph G is said to be ${\mathcal{F}}$ -free if G is H-free for every graph H in ${\mathcal{F}}$ . We study the problem of characterizing the families of graphs ${\mathcal{F}}$ such that every large enough connected ${\mathcal{F}}$ -free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1–12, 2005), Fujita et al. (J Combin Theory Ser B 96(3):315–324, 2006) and Ota et al. (J Graph Theory, 67(3):250–259, 2011), where the authors were able to characterize such graph families ${\mathcal{F}}$ restricted to the cases ${|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}$ and ${|\mathcal{F}| \leq 3}$ , respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition ${|\mathcal{F}| \leq k}$ for some k ≥ 4.     

On Induced Subgraphs with All Degrees Odd

 Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs. Received: October 5, 1998?Final version received: October 20, 2000     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Binding Numbers and Connected Factors

In this paper, we obtain some sufficient conditions based on binding number for a graph to have a connected factor with degree restrictions. Let α and k be positive integers with α + k ≥ 4. Let G be a connected graph with a spanning subgraph F, each component of which has order at least α. We show that if the binding number of G is greater than (α k − α)/(α k − α −1) (k ≥ 2) and α/(α −2) (k = 1) then G has a connected subgraph which has F and in which every vertex v has degree at most deg _F (v) + k. From the result, we derive various sufficient conditions for a graph to have a connected [a, b]-factor.     

图的连通因子

连通因子问题与Hamilton问题和信息网络有着密切的联系．1993年，首先由M.Kano就该问题在[6]中提出了许多问题和猜想，接下来他又在[16]中提出了一些猜想，本文就连通因子问题在过去十年的主要进展进行了回顾并提出了若干可进一步研究的问题和猜想．     

The Number of Edges in Induced Subgraphs of Some Distance Graphs

Mathematical Notes - We obtain new estimates for the number of edges in induced subgraphs of some distance graph.     

Subgraphs and well-quasi-ordering

Let ?? be a class of graphs and let ? be the subgraph or the induced subgraph relation. We call ? an ideal (with respect to ?) if ? implies that ?. In this paper, we study the ideals that are well-quasiordered by ?. The following are our main results. If ? is the subgraph relation, we characterize the well-quasi-ordered ideals in terms of exluding subgraphs. If?is the induced subgraph relation, we present three wellquasi-ordered ideals. We also construct examples to disprove some of the possible generalizations of our results. The connections between some of our results and digraphs are considered in this paper too.     

Connected Factors and Spanning Trees in Graphs

 Let G be a graph, and g, f, f′ be positive integer-valued functions defined on V(G). If an f′-factor of G is a spanning tree, we say that it is f′-tree. In this paper, it is shown that G contains a connected (g, f+f′−1)-factor if G has a (g, f)-factor and an f′-tree. Received: October 30, 2000 Final version received: August 20, 2002     

Punishing Factors for Finitely Connected Domains

Let Ω and Π be two finitely connected hyperbolic domains in the complex plane \Bbb C{\Bbb C} and let R(z, Ω) denote the hyperbolic radius of Ω at z and R(w, Π) the hyperbolic radius of Π at w. We consider functions f that are analytic in Ω and such that all values f(z) lie in the domain Π. This set of analytic functions is denoted by A(Ω, Π). We prove among other things that the quantities C_n(W,P) := sup_{f ? A(W,P)}sup_{z ? W}\frac|f⁽ⁿ⁾(z)| R(f(z),P)n! (R(z,W))ⁿC_n(\Omega,\Pi)\,:=\,\sup_{f\in A(\Omega,\Pi)}\sup_{z\in \Omega}\frac{\vert f^{(n)}(z)\vert\,R(f(z),\Pi)}{n!\,(R(z,\Omega))^n} are finite for all n ? \Bbb N{n \in {\Bbb N}} if and only if ∂Ω and ∂Π do not contain isolated points.     

Punishing Factors for Finitely Connected Domains

Let Ω and Π be two finitely connected hyperbolic domains in the complex plane and let R(z, Ω) denote the hyperbolic radius of Ω at z and R(w, Π) the hyperbolic radius of Π at w. We consider functions f that are analytic in Ω and such that all values f(z) lie in the domain Π. This set of analytic functions is denoted by A(Ω, Π). We prove among other things that the quantities are finite for all if and only if ∂Ω and ∂Π do not contain isolated points. This work was supported by a grant of the Deutsche Forschungsgemeinschaft for F. G. Avkhadiev.     

On the Minimal Number of Edges in Induced Subgraphs of Special Distance Graphs

Mathematical Notes - Three new theorems are proved in the paper, which give bounds for the number of edges in induced subgraphs of a special distance graph.     

Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.