A note on domination, girth and minimum degree

Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs G_i such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or G∈G_i.Our main result is that for every i∈N there is a finite set of graphs G_i such that γ?n/2-g/6-i unless G is a cycle or G∈G_i. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture.     

A note on Jordan type inequalities for hyperbolic functions

In this work the authors present some new lower and upper bounds for the functions sinx/x and x/sinhx, thus improving some inequalities put forward by Klén et al. (2010) in the paper [2].     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

A degree condition for a graph to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1 ≤ a < b. We show that G has an [a, b]-factor if δ(G) ≥ a, n ≥ 2a + b + and max {d_G(u), d_G(v) ≥ for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991), 353–361; T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992), 141–151). about the existence of a k-factor. As an immediate consequence, it shows that a conjecture of M. Kano (M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China–USA International Conference on Graph Theory and Its Application, Beijing (1993). about connected [a, b]-factors is incorrect. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 1–6, 1998     

独立数与最小度和[a，b]-因子

设G是一个图,a,b是整数且0≤a≤b,G的一个支撑子图F称为一个[a,b]-因子,若对任意的v∈V(G)有a≤dF(v)≤b.在本文中,我们给出了图存在[a,b]-因子涉及到独立数和最小度的一个充分条件,推广了前人的结果.     

A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows

Recently, a number of variants of the approximate minimum degree algorithm have been proposed that aim to efficiently order symmetric matrices containing some dense rows. We compare the performance of these variants on a range of problems and highlight their potential limitations. This leads us to propose a new variant that offers both speed and robustness. Copyright © 2009 John Wiley & Sons, Ltd.     

A note on a generalized network flow model for manufacturing process

Manufacturing network flow （MNF） is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem.     

A note on universally optimal matrices and field independence of the minimum rank of a graph

For a simple graph G on n vertices, the minimum rank of G over a field F, written as mr^F(G), is defined to be the smallest possible rank among all n×n symmetric matrices over F whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. A symmetric integer matrix A such that every off-diagonal entry is 0, 1, or -1 is called a universally optimal matrix if, for all fields F, the rank of A over F is the minimum rank of the graph of A over F. Recently, Dealba et al. [L.M. Dealba, J. Grout, L. Hogben, R. Mikkelson, K. Rasmussen, Universally optimal matrices and field independence of the minimum rank of a graph, Electron. J. Linear Algebra 18 (2009) 403-419] initiated the study of universally optimal matrices and established field independence or dependence of minimum rank for some families of graphs. In the present paper, more results on universally optimal matrices and field independence or dependence of the minimum rank of a graph are presented, and some results of Dealba et al. [5] are improved.     

A note on minimum graphs with girth pair (4, 2l + 1)

We show that the size of a smallest connected k-regular graph with girth pair (4, 2l + 1) is within a constant of (2l + 1) k/2. In so doing we disprove a conjecture of Harary and Kovacs.     

A (1 + ϵ)‐approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma*

In his seminal result, Beck gave the first algorithmic version of the Lovász Local Lemma by giving polynomial time algorithms for 2‐coloring and partitioning uniform hypergraphs. His work was later generalized by Alon, and Molloy and Reed. Recently, Czumaj and Scheideler gave an efficient algorithm for 2‐coloring nonuniform hypergraphs. But the partitioning algorithm obtained based on their second paper only applies to a more limited range of hypergraphs, so much so that their work doesn't imply the result of Beck for the uniform case. Here we give an algorithmic version of the general form of the Local Lemma which captures (almost) all applications of the results of Beck and Czumaj and Scheideler, with an overall simpler proof. In particular, if H is a nonuniform hypergraph in which every edge e_i intersects at most |e_i|2^αk other edges of size at most k, for some small constant α, then we can find a partitioning of H in expected linear time. This result implies the result of Beck for uniform hypergraphs along with a speedup in his running time. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

A note on proximinality in function spaces F(S,X)

We discuss initially how to construct a generalisation of the Lebesgue-Bochner function spaces by using a Banach lattice of real-valued functions and an appropriate lifting of the norm from this space to the more general setting. This lifting is shown to be well-defined, but the primary purpose is to discuss the notion of proximinality in this new space. In this paper, the results are derived by establishing the property of uniform convexity under suitable hypotheses. Other techniques may be found in the literature, and citations are given in the paper.     

Toughness condition for the existence of all fractional (a,b,k)-critical graphs

In this article, we obtain a sufficient condition related to toughness $\tau \left(G\right)$ for a graph to be all fractional $(a,b,k)$-critical. We prove that if $\tau \left(G\right)\ge \frac{(b^2?1)+ak}{a}$ for some nonnegative integers $a,b,k$, then $G$ is all fractional $(a,b,k)$-critical. Our result improves the known results in Liu and Zhang (2008) and Liu and Cai (2009).     

A note on a Brooks' type theorem for DP-coloring

Dvořák and Postle introduced DP-coloring of simple graphs as a generalization of list-coloring. They proved a Brooks' type theorem for DP-coloring; and Bernshteyn, Kostochka, and Pron extended it to DP-coloring of multigraphs. However, detailed structure, when a multigraph does not admit DP-coloring, was not specified. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

On an inverse scattering problem for a class Dirac operator with discontinuous coefficient and nonlinear dependence on the spectral parameter in the boundary condition

On the positive semi‐infinite interval, we obtained a generalization of the Marchenko method for a Dirac equation system with a discontinuous coefficient and a quadratic polynomial on a spectral parameter in the boundary condition. In this connection, we use an new integral representation of the Jost solution of equation systems, which does not have a ‘triangular’ form. The scattering function of the problem is defined, and its properties are examined. The Marchenko‐type main equation is obtained, and it is shown that the potential is uniquely recovered in terms the scattering function. Copyright © 2012 John Wiley & Sons, Ltd.     

A note on a variation of Doeblin's condition for uniform ergodicity of Markov chains

Summary We introduce a simple variation of Doeblin's condition, Condition D*, that assures the uniform ergodicity of a Markov chain. It is also shown that for non-homogeneous chains our conditions are equivalent to Dobrushin's weak ergodic coefficient.     

A Note on the Stability of the Integral-Differential Equation of the Hyperbolic Type in a Hilbert Space

In this paper, the initial-value problem for integral-differential equation of the hyperbolic type in a Hilbert space H is considered. The unique solvability of this problem is established. The stability estimates for the solution of this problem are obtained. The difference scheme approximately solving this problem is presented. The stability estimates for the solution of this difference scheme are obtained. In applications, the stability estimates for the solutions of the nonlocal boundary problem for one-dimensional integral-differential equation of the hyperbolic type with two dependent limits and of the local boundary problem for multidimensional integral-differential equation of the hyperbolic type with two dependent limits are obtained. The difference schemes for solving these two problems are presented. The stability estimates for the solutions of these difference schemes are obtained.