THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？

Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation

Electrical power network analysis and computation play an important role in the planning and operation of the power grid,and they are modeled mathematically as differential equations and network algebraic equations.The direct method based on Gaussian elimination theory can obtain analytical results.Two factors affect computing efficiency:the number of nonzero element fillings and the length of elimination tree.This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories.The Approximate Minimum Degree(AMD)of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length(AMDML)model.The quotient graph node with the minimum degree,which is also the minimum length of elimination tree node,is selected as the next ordering vector.Compared with AMD ordering method and other common methods,the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings;the length was decreased by about 10%compared with the AMD method.A testbed for experiment was built.The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.

Vertex-disjoint K_1+(K_1 ∪ K_2) in K_(1,4)-free Graphs with Minimum Degree at Least Four

A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.

Disjoint K-4 in claw-free graphs with minimum degree at least five

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4. The requirement of number five is necessary.

On a Classical Theorem on the Diameter and Minimum Degree of a Graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erdos, Pach, Pollack and Tuza. We use these bounds in order to study hyperbolic graphs （in the Gromov sense）. To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H（n, δ0） be the set of graphs G with n vertices and minimum degree 50, and J（n, Δ） be the set of graphs G with n vertices and maximum degree A. We study the four following extremal problems on graphs： a（n,δ0） = min{δ（G） ｜ G ∈H（n, δ0）}, b（n, δ0） =- max{δ（G）｜ e ∈H（n, δ0）}, α（n, Δ） = min{δ（G） [ G ∈ J（n, Δ）} and β（n,Δ） = max{δ（G） ] G∈Π（n,Δ）}. In particular, we obtain bounds for b（n, δ0） and we compute the precise value of a（n, δ0）, α（n, Δ） and w（n, Δ） for all values of n, r0 and A, respectively.

Erratum to “On a Classical Theorem on the Diameter and Minimum Degree of a Graph”

The original version of the article was published in [1]. Unfortunately, the original version of this article contains a mistake： in Theorem 6.2 appears that β（n, △） = （n-△ ＋ 5）/4 but the correct statement is β（n, △） = （n -△ ＋ 4）/4. In this erratum we correct the theorem and give the correct proof.

Binding Number, Minimum Degree and Bipancyclism in Bipartite Graphs

Let G =（V1,V2,E） be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B（G）,is defined to be n if G =Kn and min i∈{1,2}｜N（S）｜〈n min ｜N（S）｜/｜S｜otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B（G） 〉 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows：Let 0 〈 c 〈 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n（n is large enough） vertices such that B（G） c and δ（G）（2-c）n/（3-c）＋2/3.Then G is bipancyclic.

The Maximum and Minimum Degree of the Random r-uniform r-partite Hypergraphs

In this paper we consider the random r-uniform r-partite hypergraph model H（n1, n2,…, nr; n, p） which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where ｜Vi｜ = ni = ni（n） （1 ≤ i ≤ r） are positive integer-valued functions on n with n1 ＋n2 ＋… ＋nr =n, and each r-subset containing exactly one element in Vi （1 ≤ i ≤ r） is chosen to be a hyperedge of Hp ∈H（n1,n2,…,nr;n,p） with probability p = p（n）, all choices being independent. Let △V1 = △V1 （H） and δv1 = δv1（H） be the maximum and minimum degree of vertices in V1 of H, respectively; Xd,V1 = Xd,V1 （H）, Yd,V1 = Yd,V1 （H）, Zd,V1 = Zd,V1 （H） and Zc,d,V1=Zc,d,V1 （H） be the number of vertices in V1 of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H（n1, n2,…, nr; n,p）, Xd,V1, Yd,V1, Zd,V1, and Zc,d,V1all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D（n） such that in the space H（n1, n2,…,nr; n, p）, lim n→＋∞ P（△v1 = D（n）） = 1？ What is the range of p such that a.e., Hp ∈ H（n1,n2,...,nr;n,p） has a unique vertex in V1 with degree Av1（Hp）？ Both answers are p = o（logn1/N）, where N = r ∏ i=2 ni. The corresponding problems on δv1（Hp） also are considered, and we obtained the answers are p ≤ （1＋o（1））（logn1/N） andp=o （log n1/N）, respectively.

On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs

In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.

A NEW FINITE ELEMENT SPACE FOR EXPANDED MIXED FINITE ELEMENT METHOD

In this article,we propose a new finite element spaceΛh for the expanded mixed finite element method(EMFEM)for second-order elliptic problems to guarantee its computing capability and reduce the computation cost.The new finite element spaceΛh is designed in such a way that the strong requirement V h⊂Λh in[9]is weakened to{v h∈V h;d i v v h=0}⊂Λh so that it needs fewer degrees of freedom than its classical counterpart.Furthermore,the newΛh coupled with the Raviart-Thomas space satisfies the inf-sup condition,which is crucial to the computation of mixed methods for its close relation to the behavior of the smallest nonzero eigenvalue of the stiff matrix,and thus the existence,uniqueness and optimal approximate capability of the EMFEM solution are proved for rectangular partitions in R d,d=2,3 and for triangular partitions in R 2.Also,the solvability of the EMFEM for triangular partition in R 3 can be directly proved without the inf-sup condition.Numerical experiments are conducted to confirm these theoretical findings.

A Neighborhood Union Condition for Fractional ID-[a, b]-factor-critical Graphs

Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a＋2 b＋a（r-1）and ｜NG（x1） ∪ NG（x2） ∪…∪ NG（xr）｜ ≥（a＋b）n/（a＋2 b） for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.＇s previous result [Discussiones Mathematicae Graph Theory, 36： 409-418（2016）]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.

Super-Edge-Connectivity and Zeroth-Order Randi´c Index

Define the zeroth-order Randic index R^(0)(G)=∑x∈V(G)1/√dG1(x),where dG(x)denotes the degree of the vertex x.In this paper,we present two sufficient conditions for graphs and triangle-free graphs to be super-edge-connected in terms of the zeroth-order Randic index,respectively.

Discussion on Fractional(a,b,k)-critical Covered Graphs

A graph G is called a fractional[a,b]-covered graph if for each e∈E(G),G contains a fractional[a,b]-factor covering e.A graph G is called a fractional(a,b,k)-critical covered graph if for any W■V(G)with|W|=k,G-W is fractional[a,b]-covered,which was first defined and investigated by Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838].In this work,we proceed to study fractional(a,b,k)-critical covered graphs and derive a result on fractional(a,b,k)-critical covered graphs depending on minimum degree and neighborhoods of independent sets.