Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

Manifolds without \tfrac{1} {k} -geodesics

We will show that for any positive integer k, there exists a smooth manifold that has no -geodesic.     

The <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-dominating set of the graph G is a subset D of V (G) such that every vertex of V (G)-D is adjacent to at least k vertices in D. A k-domatic partition of G is a partition of V (G) into k-dominating sets. The maximum number of dominating sets in a k-domatic partition of G is called the k-domatic number d _k (G). In this paper, we present upper and lower bounds for the k-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number d(G) = d ₁(G).      

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

A new family of differentially 4-uniform permutations over $$\mathbb{F}_{2^{2k} }$$ for odd k

We study the differential uniformity of a class of permutations over \(\mathbb{F}_{2^n } \) with n even. These permutations are different from the inverse function as the values x^?1 are modified to be (γx)^? on some cosets of a fixed subgroup 〈γ〉 of \(\mathbb{F}_{2^n }^* \). We obtain some sufficient conditions for this kind of permutations to be differentially 4-uniform, which enable us to construct a new family of differentially 4-uniform permutations that contains many new Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) classes as checked by Magma for small numbers n. Moreover, all of the newly constructed functions are proved to possess optimal algebraic degree and relatively high nonlinearity.     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

Liftings for Haar measure on {0,1} k

We callE ⊆ {0,1} ^k projective if for some countableA ⊆κ there is anE _A ⊆ {0, 1} ^A such thatE=E _A ×{0,1} ^k\A andE _A is a projective subset of the Cantor set {0, 1} ^A . We construct a model where Haar measure on {0,1} ^k has no projective lifting (and in particular no Baire lifting) for anyκ≥ω. Research partially supported by NATO Science Fellowship. The first author would like to thank the Mathematics Department at the University of Essex for its hospitality during the academic year 1988/89 while part of this research was being carried out. This research was initiated while the second author was a postdoctoral fellow at the University of Toronto. Its completion was supported by NSF grant DMS-8505550.     

Restricted Point Configurations with Many Collinear {k}-Tuplets

   Abstract. Given k≥ 3 , denote by t' _k (N) the largest integer for which there is a set of N points in the plane, no k+1 of them on a line such that there are t' _k (N) lines, each containing exactly k of the points. Erdos (1962) raised the problem of estimating the order of magnitude of t' _k (N) . We prove that

The shift graph and the Ramsey degree of {[mathbb{N}]}^{omega}

We address several questions related to the Ramsey degree of the class of infinite structures isomorphic to the positive integers with the usual ordering. In particular we study the strength of stating that this class has finite Ramsey degree in the absence of the axiom of choice. We show that if the shift graph has finite chromatic number then this class has infinite Ramsey degree.     

Characterization of $ {\mathbb{A}_{16}} $ by a noncommuting graph

Let G be a finite non-Abelian group. We define a graph Γ _G ; called the noncommuting graph of G; with a vertex set G − Z(G) such that two vertices x and y are adjacent if and only if xy ≠ yx: Abdollahi, Akbari, and Maimani put forward the following conjecture (the AAM conjecture): If S is a finite non-Abelian simple group and G is a group such that Γ _S ≅ Γ _G ; then S ≅ G: It is still unknown if this conjecture holds for all simple finite groups with connected prime graph except \mathbbA₁₀ {\mathbb{A}_{10}} , L ₄(8), L ₄(4), and U ₄(4). In this paper, we prove that if \mathbbA₁₆ {\mathbb{A}_{16}} denotes the alternating group of degree 16; then, for any finite group G; the graph isomorphism G_\mathbbA16 @ G_G {\Gamma_{{\mathbb{A}_{16}}}} \cong {\Gamma_G} implies that \mathbbA₁₆ @ G {\mathbb{A}_{16}} \cong G .     

$\mathbb{Z}^{k}$-作用一维子系统的Lipschitz跟踪性

本文主要研究了$\mathbb{Z}^{k}$-作用一维子系统的跟踪性质. 文中运用两种等价的方式引入了$\mathbb{Z}^{k}$-作用一维子系统的伪轨以及跟踪性的概念. 对于一个闭黎曼流形上的光滑$\mathbb{Z}^{k}$-作用$T$, 我们通过诱导的非自治动力系统提出了Anosov方向的概念. 借助Bowen几何的方法, 我们证明了$T$沿着任意Anosov方向具有Lipschitz跟踪性.     

On the number of cycles of length k in a maximal planar graph

Let G be a maximal planar graph with p vertices, and let C_k(G) denote the number of cycles of length k in G. We first present tight bounds for C₃(G) and C₄(G) in terms of p. We then give bounds for C_k(G) when 5 ≤ k ≤ p, and consider in particular bounds for C_p(G), in terms of p. Some conjectures and unsolved problems are stated.