Codes and designs from triangular graphs and their line graphs

For any prime p, we consider p-ary linear codes obtained from the span over \mathbbF_p \mathbb{F}_p _p of rows of incidence matrices of triangular graphs, differences of the rows and adjacency matrices of line graphs of triangular graphs. We determine parameters of the codes, minimum words and automorphism groups. We also show that the codes can be used for full permutation decoding.     

Hulls of codes from incidence matrices of connected regular graphs

The hulls of codes from the row span over ${\mathbb{F}_p}$ , for any prime p, of incidence matrices of connected k-regular graphs are examined, and the dimension of the hull is given in terms of the dimension of the row span of A + kI over ${\mathbb{F}_p}$ , where A is an adjacency matrix for the graph. If p = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown by Dankelmann et al. (Des. Codes Cryptogr. 2012) that the hull is either {0} or has minimum weight at least 2k?2. Here we show that if the graph is strongly regular with parameter set (n, k, λ, μ), then, unless k is even and μ is odd, the binary hull is non-trivial, of minimum weight generally greater than 2k ? 2, and we construct words of low weight in the hull; if k is even and μ is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k ≥ 3, that has an ?-cycle for some ? ≥ 3, the binary hull is shown to be non-trivial with minimum weight at most 2?(k?2). Properties of the p-ary hulls are also established.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Intersections of q-ary perfect codes

The intersections of q-ary perfect codes are under study. We prove that there exist two q-ary perfect codes C ₁ and C ₂ of length N = qn + 1 such that |C ₁ ? C ₂| = k · |P _i |/p for each k ∈ {0,..., p · K ? 2, p · K}, where q = p ^r , p is prime, r ≥ 1, $n = \tfrac{{q^{m - 1} - 1}}{{q - 1}}$ , m ≥ 2, |P _i | = p ^nr(q?2)+n , and K = p ^{n(2r?1)?r(m?1)}. We show also that there exist two q-ary perfect codes of length N which are intersected by p ^nr(q?3)+n codewords.     

The number of meets between two subsets of a lattice

Let L be a lattice of divisors of an integer (isomorphically, a direct product of chains). We prove |A| |B| ? |L| |A ∧ B| for any A, B ? L, where |·| denotes cardinality and A ∧ B = {a ∧ b: a?A, b?B}. |A ∧ B| attains its minimum for fixed |A|, |B| when A and B are ideals. |·| can be replaced by certain other weight functions. When the n chains are of equal size k, the elements may be viewed as n-digit k-ary numbers. Then for fixed |A|, |B|, |A ∧ B| is minimized when A and B are the |A| and |B| smallest n-digit k-ary numbers written backwards and forwards, respectively. |A ∧ B| for these sets is determined and bounded. Related results are given, and conjectures are made.     

Symmetric diameter two graphs with affine-type vertex-quasiprimitive automorphism group

We study the class of G-symmetric graphs Γ with diameter 2, where G is an affine-type quasiprimitive group on the vertex set of Γ. These graphs arise from normal quotient analysis as basic graphs in the class of symmetric diameter 2 graphs. It is known that ${G \cong V \rtimes G_0}$ , where V is a finite-dimensional vector space over a finite field and G ₀ is an irreducible subgroup of GL (V), and Γ is a Cayley graph on V. In particular, we consider the case where ${V = \mathbb {F}_p^d}$ for some prime p and G ₀ is maximal in GL (d, p), with G ₀ belonging to the Aschbacher classes ${\mathcal {C}_2, \mathcal {C}_4, \mathcal {C}_6, \mathcal {C}_7}$ , and ${\mathcal {C}_8}$ . For ${G_0 \in \mathcal {C}_i, i = 2,4,8}$ , we determine all diameter 2 graphs which arise. For ${G_0 \in \mathcal {C}_6, \mathcal {C}_7}$ we obtain necessary conditions for diameter 2, which restrict the number of unresolved cases to be investigated, and in some special cases determine all diameter 2 graphs.     

Applications of weighted estimates of Calderon’s commutators

The paper introduces singular integral operators of a new type defined in the space L ^p with the weight function on the complex plane. For these operators, norm estimates are derived. Namely, if V is a complex-valued function on the complex plane satisfying the condition |V(z) ? V(??)| ?? w|z ? ??| and F is an entire function, then we put $$P_F^* f(z) = \mathop {\sup }\limits_{\varepsilon > 0} \left| {\int\limits_{\left| {\zeta - z} \right| > \varepsilon } {F\left( {\frac{{V(\zeta ) - V(z)}} {{\zeta - z}}} \right)\frac{{f(\zeta )}} {{\left( {\zeta - z} \right)^2 }}d\sigma (\zeta )} } \right|.$$ It is shown that if the weight function ?? is a Muckenhoupt A _p weight for 1 < p < ??, then $$\left\| {P_F^* f} \right\|_{p,\omega } \leqslant C(F,w,p)\left\| f \right\|_{p,\omega } .$$ .     

Sparse connectivity certificates via MA orderings in graphs

For an undirected multigraph G=(V,E), let α be a positive integer weight function on V. For a positive integer k, G is called (k,α)-connected if any two vertices u,v∈V remain connected after removal of any pair (Z,E^′) of a vertex subset Z⊆V-{u,v} and an edge subset E^′⊆E such that ∑_v∈Zα(v)+|E^′|<k. The (k,α)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k,α)-connected graph G, we show that a (k,α)-connected spanning subgraph of G with O(k|V|) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k,α)-connectivity.     

On sets of vectors of a finite vector space in which every subset of basis size is a basis II

This article contains a proof of the MDS conjecture for k ≤?2p ? 2. That is, that if S is a set of vectors of ${{\mathbb F}_q^k}$ in which every subset of S of size k is a basis, where q?=?p ^h , p is prime and q is not and k ≤ 2p ? 2, then |S| ≤ q?+?1. It also contains a short proof of the same fact for k?≤ p, for all q.     

Linear systems on tropical curves

A tropical curve Γ is a metric graph with possibly unbounded edges, and tropical rational functions are continuous piecewise linear functions with integer slopes. We define the complete linear system |D| of a divisor D on a tropical curve Γ analogously to the classical counterpart. We investigate the structure of |D| as a cell complex and show that linear systems are quotients of tropical modules, finitely generated by vertices of the cell complex. Using a finite set of generators, |D| defines a map from Γ to a tropical projective space, and the image can be modified to a tropical curve of degree equal to deg(D) when |D| is base point free. The tropical convex hull of the image realizes the linear system |D| as a polyhedral complex. We show that curves for which the canonical divisor is not very ample are hyperelliptic. We also show that the Picard group of a ${\mathbb{Q}}$ -tropical curve is a direct limit of critical groups of finite graphs converging to the curve.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Normal edge-transitive Cayley graphs on non-abelian groups of order 4p, where p is a prime number

We determine all connected normal edge-transitive Cayley graphs on non-abelian groups with order 4p,where p is a prime number.As a consequence we prove if |G|=2δp,δ=0,1,2 and p prime,then Γ=Cay(G,S) is a connected normal 1/2 arc-transitive Cayley graph only if G=F4p,where S is an inverse closed generating subset of G which does not contain the identity element of G and F 4p is a group with presentation F4p = a,b|ap=b4=1,b-1ab=aλ,where λ2≡-1(mod p).     

Generalized absolute Hausdorff summability of orthogonal series

For 1≦k≦2 and a sequence $\gamma :={\{\gamma(n)\}}_{n=1}^{\infty}$ that is quasi β-power monotone decreasing with ${\beta>1-\frac{1}{k}}$ , we prove the |A,γ| _k summability of an orthogonal series, where A is either a regular or Hausdorff matrix. For ${\beta>-\frac{3}{4}}$ , we give a necessary and sufficient condition for |A,γ| _k summability, where A is Hausdorff matrix. Our sufficient condition for ${\beta>-\frac{3}{4}}$ is weaker than that of Kantawala [1], ${\beta>-\frac{1}{k}}$ for |E,q,γ| _k summability; and of Leindler [4], β>?1 for |C,α,γ| _k , ${\alpha<\frac{1}{4}}$ . Also, our result generalizes the result of Spevakov [6] for |E,q,1|₁ summability.     

On Local Structure of 9- and 10-Connected Graphs

R. Halin had posed the problem of finding the largest constant c _k such that any minimally and contraction critically k-connected graph has at least c _k|V G| vertices of degree k. Twenty years later, the exact bound for k?=?4(c ₄?=?1) was found by N. Martinov and independently, by M. Fontet. For larger k, exact bounds are unknown. This paper contributes to the study of local structure of minimally and contraction critically k-connected graphs and lower boundsfor c _k . We prove that ${c_k} \geqslant \frac{1}{2}$ for k?=?9,10. This result extends the sequence of lower bounds for c _k which is equal $\frac{1}{2}$ to the values k?=?6,7,8,9,10. Bibliography: 30 titles.     

On the Burkard-Hammer condition for hamiltonian split graphs

A graph G=(V,E) is called a split graph if there exists a partition V=I∪K such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with |I|<|K|. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5≠|I|<|K| and the minimum degree δ(G)?|I|-3. For the case 5=|I|<|K|, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described.     

Congruence modularity implies cyclic terms for finite algebras

An n-ary operation f : A ⁿ → A is called cyclic if it is idempotent and ${f(a_1, a_2, a_3, \ldots , a_n) = f(a_2, a_3, \ldots , a_n, a_1)}$ for every ${a_1, \ldots, a_n \in A}$ . We prove that every finite algebra A in a congruence modular variety has a p-ary cyclic term operation for any prime p greater than |A|.     

Diameter bounds for planar graphs

The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method, we begin by proving the simpler related upper bounds (4(|V|−1)−|E|)/3 and 4|V|²/3|E| on the diameter (for connected planar graphs), which are also tight.     

Rooted directed path graphs are leaf powers

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E).     

A contraction algorithm for finding small cycle cutsets

We consider the problem of finding a minimum size cutset in a directed graph G = (V, E), i.e., a vertex set that cuts all cycles in G. Since the general problem is NP-complete we concentrate on finding small cutsets. The algorithm we suggest uses contraction operations to reduce the graph size and to identify candidates for the cutset; the complexity of the algorithm is O(|E|log|V|). This contraction algorithm is compared to Shamir-Rosen algorithm. It is shown that the class of graphs for which the contraction algorithm finds a minimum cutset (completely contractible graphs) properly contains the class of graphs for which Shamir-Rosen algorithm finds a minimum cutset (quasi-reducible graphs) and thus that the contraction algorithm is more powerful. As a by-product of this analysis we construct a hierarchy of the classes of graphs for which minimum cutsets can be found efficiently. The class of quasi-reducible graphs lies, in this hierarchy, between two classes which are closely related. This result illuminates the nature of the quasi-reducible graphs. The hierarchy constructed allows us also to compare the Wang-Lloyd-Soffa algorithm to the Shamir-Rosen algorithm and to the contraction algorithm.     

An efficient algorithm for minimumk-covers in weighted graphs

Consider an edge-weighted graphG = (V, L), and define ak-cover C as a subset of the edgesL such that each vertex inV is incident to at least one edge ofC, and|C| = k. GivenG andk, the problem is to find ak-cover of minimum weight sum. This paper presents characterizations of minimumk-covers, and shows their weight to be convex with the parameterk. An efficient algorithm is presented which generates minimumk-covers continuously as the parameterk ranges over all feasible values, together with a proof of optimality. The computational order of this algorithm is found to be|V| ? |L| ².