Conservative discretizations and parameter‐robust preconditioners for Biot and multiple‐network flux‐based poroelasticity models

The parameters in the governing system of partial differential equations of multiple‐network poroelasticity models typically vary over several orders of magnitude, making its stable discretization and efficient solution a challenging task. In this paper, we prove the uniform Ladyzhenskaya–Babu?ka–Brezzi (LBB) condition and design uniformly stable discretizations and parameter‐robust preconditioners for flux‐based formulations of multiporosity/multipermeability systems. Novel parameter‐matrix‐dependent norms that provide the key for establishing uniform LBB stability of the continuous problem are introduced. As a result, the stability estimates presented here are uniform not only with respect to the Lamé parameter λ but also to all the other model parameters, such as the permeability coefficients K_i; storage coefficients $c_{p_i}$; network transfer coefficients β_{i j},i,j = 1,…,n; the scale of the networks n; and the time step size τ. Moreover, strongly mass‐conservative discretizations that meet the required conditions for parameter‐robust LBB stability are suggested and corresponding optimal error estimates proved. The transfer of the canonical (norm‐equivalent) operator preconditioners from the continuous to the discrete level lays the foundation for optimal and fully robust iterative solution methods. The theoretical results are confirmed in numerical experiments that are motivated by practical applications.     

Local c- and E-optimal Designs for Exponential Regression Models

In this paper we investigate local E- and c-optimal designs for exponential regression models of the form . We establish a numerical method for the construction of efficient and local optimal designs, which is based on two results. First, we consider for fixed k the limit μ _i → γ (i = 1, ... , k) and show that the optimal designs converge weakly to the optimal designs in a heteroscedastic polynomial regression model. It is then demonstrated that in this model the optimal designs can be easily determined by standard numerical software. Secondly, it is proved that the support points and weights of the local optimal designs in the exponential regression model are analytic functions of the nonlinear parameters μ ₁, ... , μ _k . This result is used for the numerical calculation of the local E-optimal designs by means of a Taylor expansion for any vector (μ ₁, ... , μ _k ). It is also demonstrated that in the models under consideration E-optimal designs are usually more efficient for estimating individual parameters than D-optimal designs.     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Realizations for direct constructions of resolvable Steiner 2‐designs with block size 5

We consider direct constructions due to R. J. R. Abel and M. Greig, and to M. Buratti, for ({ν},5,1) balanced incomplete block designs. These designs are defined using the prime fields F_p for certain primes p, are 1‐rotational over G ⊕ F_p where G is a group of order 4, and are also resolvable under certain conditions. We introduce specifications to the constructions and, by means of character sum arguments, show that the constructions yield resolvable designs whenever p is sufficiently large. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:207–217, 2000     

A survey on the existence of G‐Designs

A G‐design of order n is a decomposition of the complete graph on n vertices into edge‐disjoint subgraphs isomorphic to G. We survey the current state of knowledge on the existence problem for G‐designs. This includes references to all the necessary designs and constructions, as well as a few new designs. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 373–410, 2008     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

Sufficient conditions for λ′‐optimality in graphs with girth g

For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) ? 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g ? 1, g being the girth of the graph, and show that a graph G with diameter at most g ? 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006     

Decidability for ℤ2 G‐lattices when G Extends the Noncyclic Group of Order 4

Let G be the direct sum of the noncyclic groupof order four and a cyclic groupwhoseorderisthe power pⁿ of some prime p. We show that ℤ₂ G‐lattices have a decidable theory when the cyclotomic polynomia (x) is irreducible modulo 2ℤ for every j ≤ n. More generally we discuss the decision problem for ℤ₂ G‐lattices when G is a finite group whose Sylow 2‐subgroups are isomorphic to the noncyclic group of order four.     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Convex Optimal Designs for Compound Polynomial Extrapolation

The extrapolation design problem for polynomial regression model on the design space [–1,1] is considered when the degree of the underlying polynomial model is with uncertainty. We investigate compound optimal extrapolation designs with two specific polynomial models, that is those with degrees |m, 2m}. We prove that to extrapolate at a point z, |z| > 1, the optimal convex combination of the two optimal extrapolation designs | _m ^* (z), _2m ^* (z)} for each model separately is a compound optimal extrapolation design to extrapolate at z. The results are applied to find the compound optimal discriminating designs for the two polynomial models with degree |m, 2m}, i.e., discriminating models by estimating the highest coefficient in each model. Finally, the relations between the compound optimal extrapolation design problem and certain nonlinear extremal problems for polynomials are worked out. It is shown that the solution of the compound optimal extrapolation design problem can be obtained by maximizing a (weighted) sum of two squared polynomials with degree m and 2m evaluated at the point z, |z| > 1, subject to the restriction that the sup-norm of the sum of squared polynomials is bounded.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Graphic Sequences Have Realizations Containing Bisections of Large Degree

A bisection of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph G has a bisection H such that deg_H(v) ≥ ?deg_G(v)/2? for all vertices v. We prove a degree sequence version of this conjecture: given a graphic sequence π, we show that π has a realization G containing a bisection H where deg_H(v) ≥ ?(deg_G(v) ? 1)/2? for all vertices v. This bound is very close to best possible. We use this result to provide evidence for a conjecture of Brualdi (Colloq. Int. CNRS, vol. 260, CNRS, Paris) and Busch et al. (2011), that if π and π ? k are graphic sequences, then π has a realization containing k edge‐disjoint 1‐factors. We show that if the minimum entry δ in π is at least n/2 + 2, then π has a realization containing edge‐disjoint 1‐factors. We also give a construction showing the limits of our approach in proving this conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Optimal acyclic edge‐coloring of cubic graphs

An acyclic edge‐coloring of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The acyclic chromatic index of a graph G is the smallest number of colors in an acyclic edge‐coloring of G. We prove that the acyclic chromatic index of a connected cubic graph G is 4, unless G is K₄ or K_3,3; the acyclic chromatic index of K₄ and K_3,3 is 5. This result has previously been published by Fiam?ík, but his published proof was erroneous.     

Bayesian optimal life‐testing plan under the balanced two sample type‐II progressive censoring scheme

Joint progressive censoring schemes are quite useful to conduct comparative life‐testing experiment of different competing products. Recently, Mondal and Kundu (“A New Two Sample Type‐II Progressive Censoring Scheme,” Commun Stat‐Theory Methods; 2018) introduced a joint progressive censoring scheme on two samples known as the balanced joint progressive censoring (BJPC) scheme. Optimal planning of such progressive censoring scheme is an important issue to the experimenter. This article considers optimal life‐testing plan under the BJPC scheme using the Bayesian precision and D‐optimality criteria, assuming that the lifetimes follow Weibull distribution. In order to obtain the optimal BJPC life‐testing plans, one needs to carry out an exhaustive search within the set of all admissible plans under the BJPC scheme. However, for large sample size, determination of the optimal life‐testing plan is difficult by exhaustive search technique. A metaheuristic algorithm based on the variable neighborhood search method is employed for computation of the optimal life‐testing plan. Optimal plans are provided under different scenarios. The optimal plans depend upon the values of the hyperparameters of the prior distribution. The effect of different prior information on optimal scheme is studied.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016     

Channel assignment on Cayley graphs

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n‐generated group Γ with a certain kind of presentation, then λ(G;k, 1)≤2(k+n?1). For certain values of k this bound gives the obvious optimal value for any 2n‐regular graph. A large number of groups (for instance, even Artin groups and a number of Baumslag–Solitar groups) satisfy this condition. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 169‐177, 2011     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011