Generalized orthogonal arrays: Constructions and related graphs

Generalized orthogonal arrays were first defined to provide a combinatorial characterization of (t, m, s)-nets. In this article we describe three new constructions for generalized orthogonal arrays. Two of these constructions are straightforward generalizations of constructions for orthogonal arrays and one employs new techniques. We construct families of generalized orthogonal arrays using orthogonal arrays and provide net parameters obtained from our constructions. In addition, we define a set of graphs associated with a generalized orthogonal array which provide information about the structure of the array. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 31–39, 1999     

On induced and isometric embeddings of graphs into the strong product of paths

The strong isometric dimension and the adjacent isometric dimension of graphs are compared. The concepts are equivalent for graphs of diameter 2 in which case the problem of determining these dimensions can be reduced to a covering problem with complete bipartite graphs. Using this approach several exact strong and adjacent dimensions are computed (for instance of the Petersen graph) and a positive answer is given to the Problem 4.1 of Fitzpatrick and Nowakowski [The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38] whether there is a graph G with the strong isometric dimension bigger that ⌈|V(G)|/2⌉.     

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).     

On quasi‐orthogonal cocycles

We introduce the notion of quasi‐orthogonal cocycle. This is motivated in part by the maximal determinant problem for square ‐matrices of size congruent to 2 modulo 4. Quasi‐orthogonal cocycles are analogous to the orthogonal cocycles of algebraic design theory. Equivalences with new and known combinatorial objects afforded by this analogy, such as quasi‐Hadamard groups, relative quasi‐difference sets, and certain partially balanced incomplete block designs, are proved.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

A polynomial algorithm for finding (g,f)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

On the local density problem for graphs of given odd-girth

Erdős conjectured that every n-vertex triangle-free graph contains a subset of vertices that spans at most edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to so-called Andrásfai graphs. As a consequence, Erdős' conjecture holds for every triangle-free graph G with minimum degree and if the degree condition can be relaxed to . In fact, we obtain a more general result for graphs of higher odd-girth.     

On the convergence of higher-order orthogonal iteration

The higher-order orthogonal iteration (HOOI) has been popularly used for finding a best low-multilinear rank approximation of a tensor. However, its convergence is still an open question. In this paper, we first analyse a greedy HOOI, which updates each factor matrix by selecting from the best candidates one that is closest to the current iterate. Assuming the existence of a block-nondegenerate cluster point, we establish its global iterate sequence convergence through the so-called Kurdyka–?ojasiewicz property. In addition, we show that if the starting point is sufficiently close to any block-nondegenerate globally optimal solution, the greedy HOOI produces an iterate sequence convergent to a globally optimal solution. Relating the iterate sequence by the original HOOI to that by the greedy HOOI, we then show that the original HOOI has global convergence on the multilinear subspace sequence and thus positively address the open question.     

On the two-dimensional orthogonal drawing of series-parallel graphs

It has been known that every planar 4-graph has a 2-bend 2-D orthogonal drawing, with the only exception being the octahedron, every planar 3-graph has a 1-bend 2-D orthogonal drawing with the only exception being K₄, and every outerplanar 3-graph with no triangles has a 0-bend 2-D orthogonal drawing. We show in this paper that every series-parallel 4-graph has a 1-bend 2-D orthogonal drawing.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

Tree decompositions of graphs: Saving memory in dynamic programming

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.     

On transitive Cayley graphs of strong semilattices of right (left) groups

We investigate Cayley graphs of strong semilattices of right (left) groups, of right (left) zero semigroups, and of groups. We show under which conditions they enjoy the property of automorphism vertex transitivity in analogy to Cayley graphs of groups.     

On Periodic (Co)Homology of Groups

Here we show that a countable group G has periodic cohomology of period q after some steps with the periodicity isomorphisms induced by cup product with an element in H ^q (G, ?) if and only if G has periodic homology of period q after some steps with the periodicity isomorphisms induced by cap product with an element in H ^q (G, ?). In [2 Asadollahi , J. , Hajizamani , A. , Salarian , Sh. Periodic flat resolutions and periodicity in group (co)homology. To appear in Forum Mathematicum.  [Google Scholar]] Asadollahi, Hajizamani, and Salarian showed that, if a group G is such that every flat ?G-module has finite projective dimension, then G has periodic cohomology of period q after some steps with the periodicity isomorphisms induced by cup product with an element in H ^q (G, ?) if and only if G has periodic homology of period q after some steps with the periodicity isomorphisms induced by cap product with an element in H ^q (G, C), where C is the cotorsion envelope of the trivial ?G-module ?.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On the Word Length of Commutators in GLn (R)*

Van der Kallen proved that the elementary group E_n(C[x]) does not have bounded word length with respect to the set of all elementary transvections. Later, Dennis and Vaserstein showed that the same is true, even with respect to the set of all commutators. The natural question is: Does the set of all commutators in E_n(R) have bounded word length with all elementary transvections as generators? The article provides a positive answer over a finite-dimensional commutative ring R.     

On the tangential Cauchy‐Fueter operators on nondegenerate quadratic hypersurfaces in \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}${\mathbb {H}^2}$\end{document}

On quadratic hypersurfaces in $\mathbb {H}^2$, we find the explicit forms of tangential Cauchy‐Fueter operators and associated tangential Laplacians □_b. Then by using the Fourier transformation on the associated nilpotent Lie groups of step two, we construct the relative fundamental solutions to the tangential Laplacians and Szegö kernels on the nondegenerate quadratic hypersurfaces. It is different from the complex case that the quaternionic tangential structures on the nondegenerate quadratic hypersurfaces in $\mathbb {H}^2$ cannot be reduced to one standard model and the non‐homogeneous tangential Cauchy‐Fueter equations are solvable even in many convex cases.