The crossing function of a graph

The crossing function of a graphG with orientable genusn is defined as a mapping \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) for whichf(k)=cr _k (G) the crossing number ofG on the orientable surface of genusk. It is proved that any decreasing convex function \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) with \(f(n) = \not 0\) is the crossing function of some connected graph.     

On the Elasticity of Generalized Arithmetical Congruence Monoids

Let a and b be positive integers with a ≤ b and ${a^2 \equiv a \, ({\rm mod} \, {b})}$ . The set ${M(a,b) = \{n \in \mathbb{N} | n \equiv a ({\rm mod} \, b)\} \cup \{1\}}$ is multiplicatively closed and known as an arithmetical congruence monoid (or ACM). It is well known that unique factorization need not occur in ACMs. In this paper, we investigate factorization results when we consider only elements of M(a, b) of sufficiently large size. More specifically, if M(a, b) is an ACM, we offer results concerning the elasticity of generalized ACMs (or GACMs) of the form ${M_r (a,b) = \{a +kb \in M(a,b) | k \geq r\} \cup \{1\}}$ where r is a nonnegative integer. We characterize when a generalized ACM is half-factorial (i.e. lengths of irreducible factorizations are constant). Moreover, we offer conditions, which force the elasticity to be infinite and derive a formula for finite elasticity in the case a ≠ 1.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Reflection Spaces and Corresponding Kinematic Structures

For a reflection space (P, Γ) [introduced in Karzel and Taherian (Results Math 59:213–218, 2011)] we define the notion “Reducible Subspace”, consider two subsets of ${\Gamma, \Gamma^{+} := \{a b\,|\, a,b \in P\}}$ and ${\Gamma^{-} := \{a b c\,|\, a, b, c \in P\}}$ and the map $$ \kappa : 2^{P} \to 2^{\Gamma^+} ; X \mapsto X \cdot X := \{xy\,|\, x,y \in X\}$$ We show, for each subspace S of (P, Γ), V := κ(S) is a v-subgroup (i.e. V is a subgroup of Γ⁺ with if ${\xi = xy \in V, \xi \neq 1}$ then ${x \cdot \overline{x,y}\subseteq V}$ ) if and only if S is reducible. Our main results are stated in the items 1–5 in the introduction.     

Binary Labeling of Graphs

Let G = (V, E) be a graph. A mapping f: E(G) → {0, l} ^m is called a mod 2 coding of G, if the induced mapping g: V(G) → {0, l} ^m , defined as \(g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}\) , assigns different vectors to the vertices of G. Note that all summations are mod 2. Let m(G) be the smallest number m for which a mod 2 coding of G is possible. Trivially, m(G) ≥ ?Log₂ |V|?. Recently, Aigner and Triesch proved that m(G) ≤ ?Log₂ |V|? + 4. In this paper, we determine m(G). More specifically, we prove that if each component of G has at least three vertices, then $$mG = \left\{ {\begin{array}{*{20}c} {k,} & {if \left| V \right| \ne 2^k - 2} \\ {k + 1,} & {else} \\ \end{array} ,} \right.$$ where k = ?Log₂ |V|?.     

Minimal time function and viscosity solutions

Two theorems in Ref. 1 are generalized. It is proved that, ifV(A,Γ) is the set of points that can be steered to the origin along a solution of the control systemx′=Ax?c, ifc(t)∈Γ, Γ is a compact subset ofR ⁿ , 0∈ intrelco Γ, and if a rank condition holds, then the minimal time functionT(·) is a viscosity solution of the Bellman equation $$\max \{ \left\langle {DT(x),\gamma - Ax} \right\rangle :\gamma \varepsilon co\Gamma \} - 1 = 0,x\varepsilon V(A,\Gamma )\backslash \{ 0\} ,$$ and of the Hàjek equation $$1 - \max \{ \left\langle {DT(x),\exp [ - AT(x)]} \right\rangle :\gamma \varepsilon co\Gamma \} = 0,x\varepsilon V(A,\Gamma ).$$      

Binding number and Hamiltonian(g, f)-factors in graphs

A(g, f)-factorF of a graphG is called a Hamiltonian(g, f)-factor ifF contains a Hamiltonian cycle. The binding number ofG is defined by $bind(G) = \min \left\{ {\frac{{|N_G (X)|}}{{|X|}}|\not 0 \ne X \subset V(G), N_G (X) \ne V(G)} \right\}$ . Let G be a connected graph, and let a andb be integers such that 4 ≤ a <b. Letg, f be positive integer-valued functions defined onV(G) such that a ≤g(x) < f(x) ≤ b for everyx ∈V(G). In this paper, it is proved that if $bind(G) \geqslant \frac{{(a + b - 5)(n - 1)}}{{(a - 2)n - 3(a + b - 5)}}, \nu (G) \geqslant \frac{{(a + b - 5)^2 }}{{a - 2}}$ and for any nonempty independent subset X ofV(G), thenG has a Hamiltonian(g, f)-factor.     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .     

An exact Jacobian SDP relaxation for polynomial optimization

Given polynomials f (x), g _i (x), h _j (x), we study how to minimize f (x) on the set $$S = \left\{ x \in \mathbb{R}^n:\, h_1(x) = \cdots = h_{m_1}(x) = 0,\\ g_1(x)\geq 0, \ldots, g_{m_2}(x) \geq 0 \right\}.$$ Let f _min be the minimum of f on S. Suppose S is nonsingular and f _min is achievable on S, which are true generically. This paper proposes a new type semidefinite programming (SDP) relaxation which is the first one for solving this problem exactly. First, we construct new polynomials ${\varphi_1, \ldots, \varphi_r}$ , by using the Jacobian of f, h _i , g _j , such that the above problem is equivalent to $$\begin{gathered}\underset{x\in\mathbb{R}^n}{\min} f(x) \hfill \\ \, \, {\rm s.t.}\; h_i(x) = 0, \, \varphi_j(x) = 0, \, 1\leq i \leq m_1, 1 \leq j \leq r, \hfill \\ \quad \, \, \, g_1(x)^{\nu_1}\cdots g_{m_2}(x)^{\nu_{m_2}}\geq 0, \, \quad\forall\, \nu \,\in \{0,1\}^{m_2} .\hfill \end{gathered}$$ Second, we prove that for all N big enough, the standard N-th order Lasserre’s SDP relaxation is exact for solving this equivalent problem, that is, its optimal value is equal to f _min. Some variations and examples are also shown.     

Strong approximation by Fourier series and differentiability properties of functions

ПустьΦ —N-функция Юнг а со свойствами $$\Phi (x)x^{ - 1} \downarrow 0, \exists \alpha > 1 \Phi (x)x^{ - \alpha } \uparrow (x \downarrow 0),$$ илиΦ(х)=х, {λ_k} — положи тельная, неубывающая последовательность и $$S_\Phi \{ \lambda \} = \left\{ {f:\left\| {\sum\limits_{k = 0}^\infty \Phi (\lambda _k |f - s_k |)} \right\|_\infty< \infty } \right\}.$$ В работе найдены необ ходимые и достаточны е условия для вложений $$S_\Phi \{ \lambda \} \subset W^r F(r \geqq 0),$$ , гдеF=C, L ^∞, Lip α (0<α≦1). С этой то чки зрения рассматриваются и др угие классы (например, \(W^r H^\omega ,\tilde W^r F\) ).     

Invariant random graphs with iid degrees in a general geography

Let D be a non-negative integer-valued random variable and let G = (V, E) be an infinite transitive finite-degree graph. Continuing the work of Deijfen and Meester (Adv Appl Probab 38:287–298) and Deijfen and Jonasson (Electron Comm Probab 11:336–346), we seek an Aut(G)-invariant random graph model with V as vertex set, iid degrees distributed as D and finite mean connections (i.e., the sum of the edge lengths in the graph metric of G of a given vertex has finite expectation). It is shown that if G has either polynomial growth or rapid growth, then such a random graph model exists if and only if ${\mathbb{E}[D\,R(D)] < \infty}$ . Here R(n) is the smallest possible radius of a combinatorial ball containing more than n vertices. With rapid growth we mean that the number of vertices in a ball of radius n is of at least order exp(n ^c ) for some c > 0. All known transitive graphs have either polynomial or rapid growth. It is believed that no other growth rates are possible. When G has rapid growth, the result holds also when the degrees form an arbitrary invariant process. A counter-example shows that this is not the case when G grows polynomially. For this case, we provide other, quite sharp, conditions under which the stronger statement does and does not hold respectively. Our work simplifies and generalizes the results for ${G\,=\,\mathbb {Z}}$ in [4] and proves, e.g., that with ${G\,=\,\mathbb {Z}^d}$ , there exists an invariant model with finite mean connections if and only if ${\mathbb {E}[D^{(d+1)/d}] < \infty}$ . When G has exponential growth, e.g., when G is a regular tree, the condition becomes ${\mathbb {E}[D\,\log\,D] < \infty}$ .     

О некоторых свойства х частичных сумм рядо в Фурье—Уолша—Пэли

In this paper we consider the behaviour of partial sums of Fourier—Walsh—Paley series on the group62-01. We prove the following theorems: Theorem 1. Let {n _k } _k ^=1/∞ be some increasing convex sequence of natural numbers such that $$\mathop {\lim sup}\limits_m m^{ - 1/2} \log n_m< \infty $$ . Then for anyf∈L ^∞(G) $$\left( {\frac{1}{m}\sum\limits_{j = 1}^m {|Sn_j (f;0)|^2 } } \right)^{1/2} \leqq C \cdot \left\| f \right\|_\infty $$ . Theorem 2. Let {n _k } _k ^=1/∞ be a lacunary sequence of natural numbers,n _k+1/n _k≧q>1. Then for anyfεL ^∞(G) $$\sum\limits_{j = 1}^m {|Sn_j (f;0)| \leqq C_q \cdot m^{1/2} \cdot \log n_m \cdot \left\| f \right\|_\infty } $$ . Theorems. Let µ _k =2 ^k +2 ^k-2+2 ^k-4+...+2^α ₀,α ₀=0,1. Then $$\begin{gathered} \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in L^\infty (G)\} = \{ \{ a_k \} _{k = 1}^\infty ;\sum\limits_{k = 1}^m {a_k^2 = 0(m)^2 \} .} \hfill \\ \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in C(G)\} = \{ \{ a_k \} _{k = 1}^\infty ;\sum\limits_{k = 1}^m {a_k^2 = o(m)^2 \} = } \hfill \\ = \{ \{ S_{\mu _k } (f:0\} _{k = 1}^\infty ;f \in C(G),f(0) = 0\} \hfill \\ \end{gathered} $$ . Theorem 4. {{S ₂ k(f: 0)} _k ^=1/∞ ,f∈L ^∞(G)}=m. $$\{ \{ S_{2_k } (f:0\} _{k = 1}^\infty ;f \in C(G)\} = c. \{ \{ S_{2_k } (f:0\} _{k = 1}^\infty ;f \in C(G),f(0) = 0\} = c_0 $$ .     

О НАИлУЧшЕМ ОДНОстОР ОННЕМ пРИБлИжЕНИИ цЕ лыМИ ФУНкцИьМИ

Let $$W_1 (G) = \{ x = G*y:y\varepsilon L_1 ,\parallel y\parallel _1 \leqq 1\} (L_1 = L_1 (R^1 ))$$ and $$W_1^0 (G) = \{ x = G*y\varepsilon W_1 (G), y \bot 1\} .$$ For each even functionG(t) (¦G^(v)(t)¦≦/(1+t²), v=0,1,...; t?R¹) such that its Fourier transformg(t) is 4 times monotonous on [λ, ∞) and tends to zero ast→∞, exact estimates of the best one-sided approximations by entire functions of exponential type≦σ (σ≧λ) are calculated for the classesW ₁ (G) andW ₁ ⁰ (G) inL ₁-metric.     

On Zero-Sum {\mathbb{Z}_k} -Magic Labelings of 3-Regular Graphs

Let G =  (V, E) be a finite loopless graph and let (A, +) be an abelian group with identity 0. Then an A-magic labeling of G is a function ${\phi}$ from E into A ? {0} such that for some ${a \in A, \sum_{e \in E(v)} \phi(e) = a}$ for every ${v \in V}$ , where E(v) is the set of edges incident to v. If ${\phi}$ exists such that a =  0, then G is zero-sum A-magic. Let zim(G) denote the subset of ${\mathbb{N}}$ (the positive integers) such that ${1 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}}$ -magic and ${k \geq 2 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}_k}$ -magic. We establish that if G is 3-regular, then ${zim(G) = \mathbb{N} - \{2\}}$ or ${\mathbb{N} - \{2,4\}.}$      

f-Class two graphs whose f-cores have maximum degree two

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v∈V(G) at most f(v) times.The f-core of G is the subgraph of G induced by the vertices v of degree d(v)=f(v) maxv∈V(G){ d(v)/f(v) }.In this paper,we find some necessary conditions for a simple graph,whose f-core has maximum degree two,to be of class 2 for f-colorings.     

Metrization of Weighted Graphs

We find a set of necessary and sufficient conditions under which the weight ${w: E \rightarrow \mathbb{R}^{+}}$ on the graph G = (V, E) can be extended to a pseudometric ${d : V \times V \rightarrow \mathbb{R}^{+}}$ . We describe the structure of graphs G for which the set ${\mathfrak{M}_{w}}$ of all such extensions contains a metric whenever w is strictly positive. Ordering ${\mathfrak{M}_{w}}$ by the pointwise order, we have found that the posets $({\mathfrak{M}_{w}, \leqslant)}$ contain the least elements ρ _0,w if and only if G is a complete k-partite graph with ${k \, \geqslant \, 2}$ . In this case the symmetric functions ${f : V \times V \rightarrow \mathbb{R}^{+}}$ , lying between ρ _0,w and the shortest-path pseudometric, belong to ${\mathfrak{M}_{w}}$ for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.     

A characterization of dimension-free hyperbolic geometry and the functional equation of 2-point invariants

Let X be a real inner product space of arbitrary (finite or infinite) dimension ≥ 2. Define $$P:=\{x\in X\mid\lVert x\rVert < 1\}\qquad\qquad(1)$$ and G to be the group of all bijections of P such that the images and pre-images of the following sets, called P-lines, $$(a,b):=\left\{x\in X\backslash\{a,b\} \mid\lVert a-b\rVert=\lVert a-x\rVert+\lVert x-b\rVert\right\},\qquad\qquad(2)$$ ${a,b\in X,\,a\neq b,\| a\|=1=\|b\|}$ , are again P-lines. Observe that (a, b) is given by the segment $$(a,b)=\{a +\varrho(b-a)\mid 0 < \varrho < 1\},$$ where the two points a ≠ b are on the ball B(0, 1). In Theorem 1 we prove that the geometry (P, G) is isomorphic to the hyperbolic geometry (X, M(X, hyp)) over X (see Sect. 1). In Theorem 2 we solve the Functional Equation of 2-point invariants for (P, G), showing that the notion of hyperbolic distance for (P, G) stemming from the isomorphism of Theorem 1 must be a basis of all its 2-point invariants. For definitions see the book [Benz in Classical Geometries in Modern Contexts. Geometry of Real Inner Product Spaces. Birkhäuser, Basel, 1st edn (2005) (2nd edn, 2007)], especially Sect. 2.12 and 5.11.     

An abstract Dirichlet problem in the Hilbert space

In the present paper, we consider an abstract partial differential equation of the form $\frac{{\partial ^2 u}}{{\partial t^2 }} - \frac{{\partial ^2 u}}{{\partial x^2 }} + A\left( {x,t} \right)u = f\left( {x,t} \right)$ , where $\left\{ {A\left( {x,t} \right):\left( {x,t} \right) \in \bar G} \right\}$ is a family of linear closed operators and $\bar G = G \cup \partial G,G$ is a suitable bounded region in the (x, t)-plane with boundary?G. It is assumed thatu is given on the boundary?G. The objective of this paper is to study the considered Dirichlet problem for a wide class of operatorsA(x, t). A Dirichlet problem for non-elliptic partial differential equations of higher orders is also considered.     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).