An extremal problem in geodetic graphs

An upper bound for the number of lines in a geodetic block of diameter d on p points is obtained, using some new general properties of geodetic blocks which are also of independent interest.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Bigeodetic graphs

Bigeodetic graphs, a generalization of geodetic and interval-regular graphs, are defined as graphs in which each pair of vertices has at most two paths of minimum length between them. The block cut-vertex incidence pattern of bigeodetic separable graphs are discussed. Two characterizations of bigeodetic graphs are given and some properties of these graphs are studied. Construction of planar bigeodetic blocks with given girth and diameter, and construction of hamiltonian and eulerian/nonhamiltonian and noneulerian, perfect bigeodetic blocks are discussed. The extremal bigeodetic graph of diameterd onp d + 1 vertices is constructed.On leave from A.M. Jain College, Madras University, Madras 600114, India     

Some general constructions of geodetic blocks

A general construction procedure for geodetic blocks, starting from an arbitrary geodetic block is given, which unifies and generalizes many of the known general procedures. The construction of geodetic blocks homeomorphic to a given one is also analysed and the problem of Bosák on the existence of such a graph for the Hoffman-Singleton graph is settled in the affirmative. A simple characterization theorem for geodetic blocks is given and the existence of geodetic blocks with given girth and diameter is investigated.     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

A Note About Critical Percolation on Finite Graphs

In this note we study the geometry of the largest component C₁\mathcal {C}_{1} of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137–184, 2005). There it is shown that this component is of size n ^2/3, and here we show that its diameter is n ^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886–1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \mathbbZ_n^d\mathbb{Z}_{n}^{d} (with d large and n→∞) and the Hamming cube {0,1} ⁿ .     

Bond percolation critical probability bounds for three Archimedean lattices

Rigorous bounds for the bond percolation critical probability are determined for three Archimedean lattices: .7385 < p_c((3, 12²) bond) < .7449, .6430 < p_c((4, 6, 12) bond) < .7376, .6281 < p_c((4, 8²) bond) < .7201. Consequently, the bond percolation critical probability of the (3, 12²) lattice is strictly larger than those of the other ten Archimedean lattices. Thus, the (3, 12²) bond percolation critical probability is possibly the largest of any vertex‐transitive graph with bond percolation critical probability that is strictly less than one. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 507–518, 2002     

Eine Übertragung des Satzes von Bonnet auf Regelflächen im einfach isotropen Raum

J ₃ ⁽¹⁾ . Bonnet's classical theorem about ruled surfaces in the three-dimensional Euclidean space does not hold inJ ₃ ⁽¹⁾ . To get an isotropic version of this theorem the terms geodetic line and isogonal-trajectory of the generators are replaced by new, the isotropic space adapted properties of curves on ruled surfaces.     

Ternary codes of steiner triple systems

The code over a finite field F^q of a design ?? is the space spanned by the incidence vectors of the blocks. It is shown here that if ?? is a Steiner triple system on v points, and if the integer d is such that 3^d ≤ v < 3^d+1, then the ternary code C of ?? contains a subcode that can be shortened to the ternary generalized Reed-Muller code ?_F3(2(d ? 1),d) of length 3^d. If v = 3^d and d ≥ 2, then C_? ? ?_F3(1,d)? ? _F3(2(d ? 1),d) ? C. © 1994 John Wiley & Sons, Inc.     

On pitfalls in computing the geodetic number of a graph

Given a simple connected graph G = (V, E) the geodetic closure of a subset S of V is the union of all sets of nodes lying on some geodesic (or shortest path) joining a pair of nodes . The geodetic number, denoted by g(G), is the smallest cardinality of a node set S ^* such that I[S ^*] = V. In “The geodetic number of a graph”, [Harary et al. in Math. Comput. Model. 17:89–95, 1993] propose an incorrect algorithm to find the geodetic number of a graph G. We provide counterexamples and show why the proposed approach must fail. We then develop a 0–1 integer programming model to find the geodetic number. Computational results are given.     

The Minimal Length of a Closed Geodesic Net on a Riemannian Manifold with a Nontrivial Second Homology Group

Let Mⁿ be a closed Riemannian manifold with a nontrivial second homology group. In this paper we prove that there exists a geodesic net on Mⁿ of length at most 3 diameter(Mⁿ). Moreover, this geodesic net is either a closed geodesic, consists of two geodesic loops emanating from the same point, or consists of three geodesic segments between the same endpoints. Geodesic nets can be viewed as the critical points of the length functional on the space of graphs immersed into a Riemannian manifold. One can also consider other natural functionals on the same space, in particular, the maximal length of an edge. We prove that either there exists a closed geodesic of length ≤ 2 diameter(Mⁿ), or there exists a critical point of this functional on the space of immersed θ-graphs such that the value of the functional does not exceed the diameter of Mⁿ. If n=2, then this critical θ-graph is not only immersed but embedded.Mathematics Subject Classifications (2000). 53C23, 49Q10     

Erratum to: The structure of geodetic blocks with diameter two

In our paper 1 we gave a classification of geodetic blocks of diameter two, but the proof was incorrect. Here we point out this error and give a new result about constructing geodetic blocks of diameter two. © 2004 Wiley Periodicals, Inc. J Graph Theory 46 : 79–80, 2004     

A note on 3-Steiner intervals and betweenness

The geodesic and geodesic interval, namely the set of all vertices lying on geodesics between a pair of vertices in a connected graph, is a part of folklore in metric graph theory. It is also known that Steiner trees of a (multi) set with k (k>2) vertices, generalize geodesics. In Brešar et al. (2009) [1], the authors studied the k-Steiner intervals S(u₁,u₂,…,u_k) on connected graphs (k≥3) as the k-ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to k-ary functions as follows. For any u₁,…,u_k,x,x₁,…,x_k∈V(G) which are not necessarily distinct, The authors conjectured in Brešar et al. (2009) [1] that the 3-Steiner interval on a connected graph G satisfies the betweenness axiom (b2) if and only if each block of G is geodetic of diameter at most 2. In this paper we settle this conjecture. For this we show that there exists an isometric cycle of length 2k+1, k>2, in every geodetic block of diameter at least 3. We also introduce another axiom (b2(2)), which is meaningful only to 3-Steiner intervals and show that this axiom is equivalent to the monotone axiom.     

On the existence of (3,λ)‐semiframes of type 3u

A (k,λ)‐semiframe of type g^u is a (k,λ)‐group‐divisible design of type g^u (??, ??, ??), in which the collection of blocks ?? can be written as a disjoint union ??=??∪?? where ?? is partitioned into parallel classes of ?? and ?? is partitioned into holey parallel classes, each holey parallel class being a partition of ??\G_j for some G_j∈??. In this paper, we shall prove that the necessary conditions for (3,λ)‐semiframes of type 3^u are also sufficient with one exception. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 253–265, 2009     

Truncated Transversal Designs: A New Lower Bound on the Number of Idempotent MOLS of Side n

A truncated transversal design TTD of type g^km¹ is a {k, k+1}-GDD of type g^km¹ in which each point on the group of size m lies only in blocks of size k+1. Thus a TTD of type g^km¹ is equivalent to a transversal design TD (k, g) having m disjoint parallel classes of blocks. We employ a new construction developed by the author (1993, J. Combin. Des.1, 15–26) to show that if g₁<g₂ and if there exists a TD (k, g₁) and a TD (k+1, g₂), then there exists a TTD of type (g₁g₂)^km¹ for any 0m(g₂ div g₁) g²₁. As a corollary, we obtain a new lower bound on the number of mutually orthogonal idempotent latin squares of side g: if g₁<g₂ and there exist r MOLS of side g₁ and r+1 MOLS of side g₂ , then N(1 ^g₁g₂)r.     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

On the Dirichlet Problem for the Nonlinear Diffusion Equation in Non-smooth Domains

We study the Dirichlet problem for the parabolic equation u_t = Δu^m, m > 0, in a bounded, non-cylindrical and non-smooth domain Ω ^{N + 1}, N ≥ 2. Existence and boundary regularity results are established. We introduce a notion of parabolic modulus of left-lower (or left-upper) semicontinuity at the points of the lateral boundary manifold and show that the upper (or lower) Hölder condition on it plays a crucial role for the boundary continuity of the constructed solution. The Hölder exponent is critical as in the classical theory of the one-dimensional heat equation u_t = u_xx.     

Pyramids in the complex projective plane

We study the critical points of the diameter functional on the n-fold Cartesian product of the complex projective plane C P ² with the Fubini-Study metric. Such critical points arise in the calculation of a metric invariant called the filling radius, and are akin to the critical points of the distance function. We study a special family of such critical points, P _kC P ¹C P ², k=1,2... We show that P _k is a local minimum of by verifying the positivity of the Hessian of (a smooth approximation to) at P _k. For this purpose, we use Shirokov's law of cosines and the holonomy of the normal bundle of C P ¹C P ². We also exhibit a critical point of , given by a subset which is not contained in any totally geodesic submanifold of C P ².     

On the existence of a field of stress rates in a hardening elastic-plastic medium : PMM vol. 38, n 6, 1974, pp. 1114–1121

The boundary value problem for the stress rates and rates of change fields in the quasi-static motion of a volume V of an elastic-plastic medium [1] consists of finding the pairs σ_ij^., _ij^. related by the governing equations of an appropriate model; here the σ_ij^. should be statically admissible i.e. should satisfy the equations and boundary conditions σ_ij=−X/._i; /.σ_ijn_j|S_p=p_i and _ij should be kinematically admissible i.e. 2/._ij = v_ij + v_ji, where v_i|S_u = u_io Here S_p and S_u are nonintersecting parts of the boundary of the volume V, X_i, p_i, u_i/.o are specified functions. The question of the existence of a solution of this problem reduces to the question of the functional reaching the lower bound in a set of kinematically admissible /._ij^o and statically admissible σ_ij/.^/*. However, its lower bound may not be reached if in the minimization we limit ourselves only to smooth fields. It is proposed to augment the set of admissible fields σ_ij/.^/*,_ij/.^o by closing them in the norm L₂ (for v_i^o this corresponds to closure in the norm II¹). Some properties of the functional I (σ_ij^*,_ij/.) are considered in the augmented set of admissible fields. It is shown that the equivalence of the two problems is conserved, where I (σ_ij^*,_ij⁰ can be minimized in σ_ij^/*,_ij^o or in σ_ij^/*,_ij/.^o, The lower bound is reached in each of three cases, at a single point. From the fact that u_i^o belongs to the Sobolev space W₂⁽¹⁾, there results the absence of surfaces of velocity discontinuity. Variational principles have been used in plasticity theory to construct models [2] and to investigate the existence and properties of solutions [1, 3].     

Multiple Positive Solutions for Eigenvalue Problems of Hemivariational Inequalities

We study a nonlinear eigenvalue problem with a nonsmooth potential. The subgradients of the potential are only positive near the origin (from above) and near +∞. Also the subdifferential is not necessarily monotone (i.e. the potential is not convex). Using variational techniques and the method of upper and lower solutions, we establish the existence of at least two strictly positive smooth solutions for all the parameters in an interval. Our approach uses the nonsmooth critical point theory for locally Lipschitz functions. A byproduct of our analysis is a generalization of a result of Brezis-Nirenberg (CRAS, 317 (1993)) on H¹₀ versus C¹₀ minimizers of a C¹-functional.