Current graphs and bi-embeddings

Let N(γ,γ′) denote the size of the smallest complete graph which cannot be edge-partitioned into two parts embeddable in closed orientable surfaces of genera γ,γ′ respectively. The theory of current graphs is used to determine the values of N(γ,γ′) in certain cases. Some related block designs are discussed.     

A partition approach to Vizing's conjecture

In 1963, Vizing [Vichysl.Sistemy 9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P₂(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P₂(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P₂(H) + P₂(G)(γ(H) − P₂(H)). © 1996 John Wiley & Sons, Inc.     

Shape sensitivity analysis of stress intensity factors by Generalized J-integrals

We consider an elastic plate with the non-deformed shape Ω_Σ := Ω \ Σ, where Ω is a domain bounded by a smooth closed curve Γ and Σ ⊂ Ω is a curve with the end points {γ₁, γ₂}. If the force g is given on the part Γ_N of Γ, the displacement u is fixed on Γ_D := Γ \ Γ_N and the body force f is given in Ω, then the displacement vector u(x) = (u₁(x), u₂(x)) has unbounded derivatives (stress singularities) near γ_k, k = 1, 2    u(x) = ∑²_{k, l=1} K_l(γ_k)r^1/2_kS^C_kl(θ_k) + u_R(x)     near γ_k. Here (r_k, θ_k) denote local curvilinear polar co-ordinates near γ_k, k = 1, 2, S^C_kl (θ_k) are smooth functions defined on [−π, π] and u_R(x) ∈ {H²(near γ_k)}². The constants K_l(γ_k),   l = 1, 2, which are called the stress intensity factors at γ_k (abbr. SIFs), are important parameters in fracture mechanics. We notice that the stress intensity factors K_l(γ_k) (l = 1, 2;  k = 1, 2) are functionals K_l(γ_k) = K_l(γ_k; ℒ︁, Ω, Σ) depending on the load ℒ︁, the shape of the plate Ω and the shape of the crack Σ. We say that the crack Σ is safe, if K_l(γ_k; Ω)² + K₂(γ_k; Ω)² < RẼ. By a small change of Ω the shape Σ can change to a dangerous one, i.e. we have K₁(γ_k; Ω)² + K₂(γ_k; Ω)² ⩾ RẼ. Therefore it is important to know how K_l(γ_k) depends on the shape of Ω. For this reason, we calculate the Gâteaux derivative of K_l(γ_k) under a class of domain perturbations which includes the approximation of domains by polygonal domains and the Hadamard's parametrization Γ(τ) := {x + τϕ(x)n(x);  x ∈ Γ}, where ϕ is a function on Γ and n is the outward unit normal on Γ. The calculations are quite delicate because of the occurrence of additional stress singularities at the collision points {γ₃, γ₄} = Γ _D ∩ Γ _N. The result is derived by the combination of the weight function method and the Generalized J-integral technique (abbr. GJ-integral technique). The GJ-integrals have been proposed by the first author in order to express the variation of energy (energy release rate) by extension of a crack in a 3D-elastic body. This paper begins with the weak solution of the crack problem, the weight function representation of SIF's, GJ-integral technique and finish with the shape sensitivity analysis of SIF's. GJ-integral J_ω(u; X) is the sum of the P-integral (line integral) P_ω(u, X) and the R-integral (area integral) R_ω(u, X). With the help of the GJ-integral technique we derive an R-integral expression for the shape derivative of the potential energy which is valid for all displacement fields u ∈ H¹. Using the property that the GJ-integral vanishes for all regular fields u ∈ H² we convert the R-integral expression for the shape derivative to a P-integral expression. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

New decay estimates for linear damped wave equations and its application to nonlinear problem

We present new decay estimates of solutions for the mixed problem of the equation v_tt?v_xx+v_t=0, which has the weighted initial data [v₀,v₁]∈(H¹₀(0,∞) ∩L^1,γ(0,∞)) × (L²(0,∞)∩L^1,γ(0,∞)) (for definition of L^1,γ(0,∞), see below) satisfying γ∈[0,1]. Similar decay estimates are also derived to the Cauchy problem in ?^N for u_tt?Δu+u_t=0 with the weighted initial data. Finally, these decay estimates can be applied to the one dimensional critical exponent problem for a semilinear damped wave equation on the half line. Copyright © 2004 John Wiley & Sons, Ltd.     

On Crawley Modules

A curve Xis said to be of type (iV, γ) if it is an iV-sheeted covering of a curve of genus γ with at least one totally ramified point. A numerical semigroup His said to be of type (iV, γ) if it has γ positive multiples of Nin [N, 2N_J] such that its γth element is 2Nγ and (2γ+1)NεH. If the genus of X is large enough and N is prime, X is of type (TV, γ) if and only if there is a point P6 X such that the Weierstrass semigroup at P is of type (N, γ) (this generalizes the case of double coverings of curves). Using the proof of this result and the Buchweitz's semigroup, we can construct numerical semigroups that cannot be realized as Weierstrass semigroups although they might satisfy Buchweitz's criterion     

The ratio of the irredundance number and the domination number for block-cactus graphs

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998     

On Radicals with Amitsur Property

Abstract

A radical γ has the Amitsur property, if γ(A[x]) = (γ(A[x]) ∩ A)[x] for every ring A. To any radical γ with Amitsur property we construct the smallest radical γ ^x which coincides with γ on polynomial rings. Distinct special radicals with Amitsur property are given which coincide on simple rings and on polynomial rings, answering thus a stronger version of M. Ferrero's problem. Radicals γ with Amitsur property are characterized which satisfy A[x, y] ∈ γ whenever A[x] ∈ γ.     

The degree sequence of a scale‐free random graph process

Recently, Barabási and Albert [2] suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P(d) of vertices with degree d should obey a power law P(d)αd^?γ. They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P(d) asymptotically for all d≤n^1/15, where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001     

Invariant imbedding applied to a class of freholm integral equations

The objective of this paper is the rigorous derivation of an invariant imbedding algorithm for the solution of the integral equation

$\text{ø(z)g(z)+γ?}{}^{\mathrm{\infty }}{}_0\text{K}\text{(∣z-z′∣)ø(z′)dz′}$

for

$\text{z?0}$

, under suitable restrictions on g, K, and γ. First a set of conditions is determined under which Eq. (1) has a unique solution. The function ø(z) is shown to be approximated almost uniformly for Y=0 and as x→∞ by the solution of     

The normalizer of γ1(N) in psl2(R)

We find the full normalizer of γ₁(N) in psl₂(R).     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

Representing products of polyhedra by products of edge-colored graphs

Given an (m + 1)-colored graph ( Γ γ′) and an (n + 1)-colored graph (, γ″), representing two polyhedra P′, P″ respectively, we present a direct construction of an (m + n+1)-colored graph ( Γ ′? Γ ″, γ′ ? γ″), which represents the product P ′ × P ″. Some examples, applications, and conjectures about the genus of manifold products are also presented. © 1993 John Wiley & Sons, Inc.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

Multiparameter acoustic imaging in the born approximation

Samples of biological tissue are modelled as inhomogeneous fluids with density ?(X) and sound speed c(x) at point x. The samples are contained in the sphere |x| ? δ and it is assumed that ?(x) ? ?₀ = 1 and c(x) ? c₀ = 1 for |x| ? δ, and |γ_n(x)| ? 1 and |?γ?(x)| ? 1 where γ?(x) = ?(x) ? 1 and γ_n(x) = c^?2(x) ? 1. The samples are insonified by plane pulses s(x · θ₀ – t) where x = |θ₀| = 1 and the scattered pulse is shown to have the form |x|^?1 e_s(|x| – t, θ, θ₀) in the far field, where x = |x| θ. The response e_s(τ, θ, θ₀) is measurable. The goal of the work is to construct the sample parameters γn and γ? from e_s(τ, θ, θ₀) for suitable choiches of s, θ and θ₀. In the limiting case of constant density: γ?(x)_? 0 it is shown that Where δ represents the Dirac δ and S² is the unit sphere |θ| = 1. Analogous formulas, based on two sets of measurements, are derived for the case of variable c(x) and ?(x).     

Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

EXTREMUM AGGREGATES OF MINIMAL 0-DOMINATING FUNCTIONS OF GRAPHS

Abstract

A 0-dominating function 0DF of a graph G = (V,E) is a function f: V → [0,1] such that Σ _xεN(v) f(x) ≥ 1 for each ν ε V with f(v) = 0. The aggregate of a 0DF f is defined by ag(f) = Σ_vεV f(v) and the infimum and supremum of the set of aggregates over all minimal 0DFs of a graph are denoted by γ₀ and Γ₀ respectively. We prove some properties of minimal 0DFs and determine γ₀ and Γ₀ for some classes of graphs.     

Graph-theoretic parameters concerning domination,independence, and irredundance

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah Gwith p vertices and no isolated vertices, i(G) ≤ p-γ(G) + 1 - ?(p - γ(G))/γ(G)?.     

Long cycles in subgraphs of (pseudo)random directed graphs

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant c = c(γ) such that the following holds. Let G = (V, E) be a (pseudo)random directed graph on n vertices and with at least a linear number of edges, and let G′ be a subgraph of G with (1/2 + γ)|E| edges. Then G′ contains a directed cycle of length at least (c ? o(1))n. Moreover, there is a subgraph G′′of G with (1/2 + γ ? o(1))|E| edges that does not contain a cycle of length at least cn. © 2011 Wiley Periodicals, Inc. J Graph Theory 70: 284–296, 2012     

The Bar-Radical of a Class of Almost Alternative Baric Algebras

In this article we prove that, if (U, ω) is a finite dimensional baric algebra of (γ, δ) type over a field F of characteristic ≠ 2,3,5 such that γ² ? δ² + δ = 1 and δ ≠ 0,1, then rad(U) = R(U) ∩ (bar(U))², where R(U) is the nilradical (maximal nil ideal) of U.     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001