Search

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. A reduced graph $G$ is said to be maximal if any reduced graph containing $G$ as a proper induced subgraph has a higher rank. The main intent of this paper is to present some results on maximal graphs. First, we introduce a characterization of maximal trees (a reduced tree is a maximal tree if it is not a proper subtree of a reduced tree with the same rank). Next, we give a near-complete characterization of maximal `generalized friendship graphs.' Finally, we present an enumeration of all maximal graphs with ranks $8$ and $9$. The ranks up to $7$ were already done by Lepovi\'c (1990), Ellingham (1993), and Lazi\'c (2010)., Comment: 18 pages, final version, to appear in Discrete Mathematics

Let $v\geq6$ be an integer with $v\equiv2 \pmod 4$. In this paper, we introduce a new partitioning of the set of all $3$-subsets of a $v$-set into some simple trades.

A $[t]$-trade is a pair $T=(T_+, T_-)$ of disjoint collections of subsets (blocks) of a $v$-set $V$ such that for every $0\le i\le t$, any $i$-subset of $V$ is included in the same number of blocks of $T_+$ and of $T_-$. It follows that $|T_+| = |T_-|$ and this common value is called the volume of $T$. If we restrict all the blocks to have the same size, we obtain the classical $t$-trades as a special case of $[t]$-trades. It is known that the minimum volume of a nonempty $[t]$-trade is $2^t$. Simple $[t]$-trades (i.e., those with no repeated blocks) correspond to a Boolean function of degree at most $v-t-1$. From the characterization of Kasami--Tokura of such functions with small number of ones, it is known that any simple $[t]$-trade of volume at most $2\cdot2^t$ belongs to one of two affine types, called Type\,(A) and Type\,(B) where Type\,(A) $[t]$-trades are known to exist. By considering the affine rank, we prove that $[t]$-trades of Type\,(B) do not exist. Further, we derive the spectrum of volumes of simple trades up to $2.5\cdot 2^t$, extending the known result for volumes less than $2\cdot 2^t$. We also give a characterization of "small" $[t]$-trades for $t=1,2$. Finally, an algorithm to produce $[t]$-trades for specified $t$, $v$ is given. The result of the implementation of the algorithm for $t\le4$, $v\le7$ is reported., Comment: 30 pages, final version, to appear in Electron. J. Combin

Let $\D_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$. Let $d\in\D_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$. The matrix $C(d)=R(d)-\frac{1}{k}N(d)N(d)^\top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $\mu_1(d),...,\mu_{v-1}(d)$. Let $\D$ be the class of all binary designs of $\D_{v,b,k}$. We prove that if there is a design $d^*\in\D$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $d\in\D$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $d\in\D$, then for all $p>0$, $d^*$ minimizes $(\sum_{i=1}^{v-1}\mu_i(d)^{-p})^{1/p}$ over $d\in\D$. In the context of optimal design theory, this means that if there is a design $d^*\in\D$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in $\D$, then $d^*$ is $\Phi_p$-optimal in $\D$ for all $p>0$. As an application, we demonstrate the $\Phi_p$-optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming., Comment: 14 pages, final version

Let $G$ be a graph. A zero-sum flow in $G$ is an assignment of nonzero real number to the edges such that the sum of the values of all edges incident with each vertex is zero. Let $k$ be naturel number. A zero-sum $k$-flow is a flow with value from the set $\{\pm 1, \pm 2,..., \pm(k-1)\}$. It has been conjectured that every $r$-regular graph, $r\geq 3$, admits a zero-sum 5-flow. In this paper we give an affirmative answer to this conjecture, exept for r=5.

Let $X$ be a $v$-set, $\B$ a set of 3-subsets (triples) of $X$, and $\B^+\cup\B^-$ a partition of $\B$ with $|\B^-|=s$. The pair $(X,\B)$ is called a simple signed Steiner triple system, denoted by ST$(v,s)$, if the number of occurrences of every 2-subset of $X$ in triples $B\in\B^+$ is one more than the number of occurrences in triples $B\in\B^-$. In this paper we prove that $\st(v,s)$ exists if and only if $v\equiv1,3\pmod6$, $v\ne7$, and $s\in\{0,1,...,s_v-6,s_v-4,s_v\}$, where $s_v=v(v-1)(v-3)/12$ and for $v=7$, $s\in\{0,2,3,5,6,8,14\}$., Comment: 11 pages, 1 table. Final version. To appear in Journal of Combinatorial Designs

Given integers $t$, $k$, and $v$ such that $0\leq t\leq k\leq v$, let $W_{tk}(v)$ be the inclusion matrix of $t$-subsets vs. $k$-subsets of a $v$-set. We modify slightly the concept of standard tableau to study the notion of rank of a finite set of positive integers which was introduced by Frankl. Utilizing this, a decomposition of the poset $2^{[v]}$ into symmetric skipless chains is given. Based on this decomposition, we construct an inclusion matrix, denoted by $W_{\bar{t}k}(v)$, which is row-equivalent to $W_{tk}(v)$. Its Smith normal form is determined. As applications, Wilson's diagonal form of $W_{tk}(v)$ is obtained as well as a new proof of the well known theorem on the necessary and sufficient conditions for existence of integral solutions of the system $W_{tk}\bf{x}=\bf{b}$ due to Wilson. Finally we present anotherinclusion matrix with similar properties to those of $W_{\bar{t}k}(v)$ which is in some way equivalent to $W_{tk}(v)$., Comment: Accepted for publication in Journal of Combinatorial Theory, Series A