The Spectrum of Tetrahedral Quadruple Systems

An ordered analogue of quadruple systems is tetrahedral quadruple systems. A tetrahedral quadruple system of order v and index λ, TQS(v, λ), is a pair (S, T){(S, \mathcal{T})} where S is a finite set of v elements and T{\mathcal{T}} is a family of oriented tetrahedrons of elements of S called blocks, such that every directed 3-cycle on S is contained in exactly λ blocks of T{\mathcal{T}} . When λ = 1, the spectrum problem of TQS(v, 1) has been completely determined. It is proved that a TQS(v, λ) exists if and only if λ(v − 1)(v − 2) ≡ 0 (mod 3), λv(v − 1)(v − 2) ≡ 0 (mod 4) and v ≥ 4.     

三类有向三元系之间关系的一种猜想

一个Mendelsohn (Directed, 或Hybrid)三元系 MTS$(v, \lambda)$~(DTS$(v, \lambda)$,或HTS$(v,\lambda))$, 是由$v$元集$X$ 上的一些循环（可迁，或循环和可迁）三元组(简称区组)构成的集合${\cal B}$, 使得$X$上每个由不同元素组成的有序对都恰在 ${\cal B}$的$\lambda$个区组中出现.本文主要讨论了这三类有向三元系之间的一种关联关系，给出猜想：任意MTS$(v,\lambda)$的区组关联图$G(\     

The spectrum for overlarge sets of hybrid triple systems

A hybrid triple system of order v and index λ,denoted by HTS(v,λ),is a pair(X,B) where X is a v-set and B is a collection of cyclic triples and transitive triples on X,such that every ordered pair of X belongs to λ triples of B. An overlarge set of disjoint HTS(v,λ),denoted by OLHTS(v,λ),is a collection {(Y \{y},Ai)}i,such that Y is a(v+1)-set,each(Y \{y},Ai) is an HTS(v,λ) and all Ais form a partition of all cyclic triples and transitive triples on Y.In this paper,we shall discuss the existence problem of OLHTS(v,λ) and give the following conclusion: there exists an OLHTS(v,λ) if and only if λ=1,2,4,v ≡ 0,1(mod 3) and v≥4.     

带弦的圈是协调图

称具有ｅ条边的简单图Ｇ为协调图，若存在由Ｇ的顶点集到模ｅ的整数群Ｚｅ的一个单射ｈ，使得导出映射ｈ＾＊：ｈ＾＊（ｕｖ）≡ｈ（ｕ）＋ｈ（ｖ）（ｍｏｄ ｅ）是一个由Ｇ的边集到Ｚｅ的双射，带弦的圈Ｃ′ｎ是由含ｎ个顶点的圈Ｃｎ上添一条连结两个不相邻顶点的边而得到的图。本文中证明了，除了ｎ＝６且弦端点在Ｃｎ上的距离为２的情况外，所有带弦的圈都是协调图。     

K_(2,3)的多重多部图设计的构造

λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2).     

Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001     

A Completion of the Spectrum for the Overlarge Sets of Pure Mendelsohn Triple Systems

A pure Mendelsohn triple system of order v, denoted by PMTS(v), is a pair \((X,\mathcal {B})\) where X is a v-set and \(\mathcal {B}\) is a collection of cyclic triples on X such that every ordered pair of X belongs to exactly one triple of \(\mathcal {B}\) and if \(\langle a,b,c\rangle \in \mathcal {B}\) implies \(\langle c,b,a\rangle \notin \mathcal {B}\). An overlarge set of PMTS(v), denoted by OLPMTS(v), is a collection \(\{(Y{\setminus }\{y_i\},{\mathcal {A}}_i)\}_i\), where Y is a \((v+1)\)-set, \(y_i\in Y\), each \((Y{\setminus }\{y_i\},{\mathcal {A}}_i)\) is a PMTS(v) and these \({\mathcal {A}}_i\)s form a partition of all cyclic triples on Y. It is shown in [3] that there exists an OLPMTS(v) for \(v\equiv 1,3\) (mod 6), \(v>3\), or \(v \equiv 0,4\) (mod 12). In this paper, we shall discuss the existence problem of OLPMTS(v)s for \(v\equiv 6,10\) (mod 12) and get the following conclusion: there exists an OLPMTS(v) if and only if \(v\equiv 0,1\) (mod 3), \(v>3\) and \(v\ne 6\).     

Pure tetrahedral quadruple systems with index two

An oriented tetrahedron defined on four vertices is a set of four cyclic triples with the property that any ordered pair of vertices is contained in exactly one of the cyclic triples. A tetrahedral quadruple system of order $n$ with index $\lambda$, denoted by ${\text{TQS}}_{\lambda }\left(n\right)$, is a pair $\left(X,\mathrm{?}\right)$, where $X$ is an $n$‐set and $\mathrm{?}$ is a set of oriented tetrahedra (blocks) such that every cyclic triple on $X$ is contained in exactly $\lambda$ members of $\mathrm{?}$. A ${\text{TQS}}_{\lambda }\left(n\right)$ is pure if there do not exist two blocks with the same vertex set. When $\lambda =1$, the spectrum of a pure TQS $\left(n\right)$ has been completely determined by Ji. In this paper, we show that there exists a pure ${\text{TQS}}_2\left(n\right)$ if and only if $n\equiv 1,2\left(\mathrm{mod}3\right)$ and $n\ge 7$. A corollary is that a simple ${\text{QS}}_4\left(n\right)$ also exists if and only if $n\equiv 1,2\left(\mathrm{mod}3\right)$ and $n\ge 7$.     

Characterizing directed path graphs by forbidden asteroids

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non‐adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex‐disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:103‐112, 2011     

Steiner almost self-complementary graphs and halving near-Steiner triple systems

We show that for every admissible order v≡0 or there exists a near-Steiner triple system of order v that can be halved. As a corollary we obtain that a Steiner almost self-complementary graph with n vertices exists if and only if n≡0 or .     

THE EXISTENCE OF OVERLARGE SETS OF IDEMPOTENT QUASIGROUPS

A idempotent quasigroup (Q, o) of order n is equivalent to an n(n-1)×3 partial orthogonal array in which all of rows consist of 3 distinct elements. Let X be a (n+1)-set. Denote by T(n+1) the set of (n+1)n(n-1) ordered triples of X with the property that the 3 coordinates of each ordered triple are distinct. An overlarge set of idempotent quasigroups of order n is a partition of T(n+1) into n+1 n(n-1)×3 partial orthogonal arrays A_x, x∈X based on X\{x}. This article gives an almost complete solution of overlarge sets of idempotent quasigroups.     

Extended skolem sequences

A k-extended Skolem sequence of order n is an integer sequence (s₁, s₂,…, s_2n+1) in which s_k = 0 and for each j ? {1,…,n}, there exists a unique i ? {1,…, 2n} such that s_i = s_i+j = j. We show that such a sequence exists if and only if either 1) k is odd and n ≡ 0 or 1 (mod 4) or (2) k is even and n ≡ 2 or 3 (mod 4). The same conditions are also shown to be necessary and sufficient for the existence of excess Skolem sequences. Finally, we use extended Skolem sequences to construct maximal cyclic partial triple systems. © 1995 John Wiley & Sons, Inc.     

Ramification points of double coverings of curves and Weierstrass points

Summary Let π: X→C be a double covering with X smooth curve and C elliptic curve. Let R(π)⊂X be the ramification locus of π. Every P∈R(π) is a Weierstrass point of X and we study the triples (C, π, X) for which the set of corresponding Weierstrass points have certain semigroups of non-gaps. We study the same problem also for triple cyclic coverings of C. Entrata in Redazione il 17 luglio 1998. The authors were partially supported by MURST and GNSAGA of CNR (Italy).     

The size of minimum 3‐trees

A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on n vertices is exactly . © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 103–114, 2007     

Frame Self-orthogonal Mendelsohn Triple Systems

A Mendelsohn triple system of order ν, MTS(ν) for short, is a pair (X, B) where X is a ν-set (of points) and B is a collection of cyclic triples on X such that every ordered pair of distinct points from X appears in exactly one cyclic triple of B. The cyclic triple (a, b, c) contains the ordered pairs (a, b), (b, c) and (c, a). An MTS(ν) corresponds to an idempotent semisymmetric Latin square (quasigroup) of order ν. An MTS(ν) is called frame self-orthogonal, FSOMTS for short, if its associated semisymmetric Latin square is frame self-orthogonal. It is known that an FSOMTS(1 ⁿ ) exists for all n≡1 (mod 3) except n=10 and for all n≥15, n≡0 (mod 3) with possible exception that n=18. In this paper, it is shown that (i) an FSOMTS(2 ⁿ ) exists if and only if n≡0,1 (mod 3) and n>5 with possible exceptions n∈{9, 27, 33, 39}; (ii) an FSOMTS(3 ⁿ ) exists if and only if n≥4, with possible exceptions that n∈{6, 14, 18, 19}. *Research supported by NSFC 10371002 *Partially supported by National Science Foundation under Grant CCR-0098093     

关于奇算术图

本文讨论了$n$个$m$长圈有一个公共结点图$C^n_m$, $n$个$m$长圈与$t$长路有一个公共结点图$C^n_m\cdot P_t$, $n$个$m$阶完全图有一个公共结点图$K^n_m$和星形图的同胚图的奇算术性问题.给出了完全图,完全二部图和圈是奇算术的充要条件.     

Recognizing String Graphs Is Decidable

Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

Trinal Decompositions of Steiner Triple Systems into Triangles

It is well known that when or , there exists a Steiner triple system (STS) of order n decomposable into triangles (three pairwise intersecting triples whose intersection is empty). A triangle in an STS determines naturally two more triples: the triple of “vertices” , and the triple of “midpoints” . The number of these triples in both cases, that of “vertex” triples (inner) or that of “midpoint triples” (outer), equals one‐third of the number of triples in the STS. In this paper, we consider a new problem of trinal decompositions of an STS into triangles. In this problem, one asks for three distinct decompositions of an STS of order n into triangles such that the union of the three collections of inner triples (outer triples, respectively) from the three decompositions form the set of triples of an STS of the same order. These decompositions are called trinal inner and trinal outer decompositions, respectively. We settle the existence question for trinal inner decompositions completely, and for trinal outer decompositions with two possible exceptions.     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

Doyen–Wilson theorem for perfect hexagon triple systems

The graph consisting of the three 3-cycles (or triples) (a,b,c), (c,d,e), and (e,f,a), where a,b,c,d,e and f are distinct is called a hexagon triple. The 3-cycle (a,c,e) is called an inside 3-cycle; and the 3-cycles (a,b,c), (c,d,e), and (e,f,a) are called outside 3-cycles. A hexagon triple system of order v is a pair (X,C), where C is a collection of edge disjoint hexagon triples which partitions the edge set of 3K_v. Note that the outside 3-cycles form a 3-fold triple system. If the hexagon triple system has the additional property that the collection of inside 3-cycles (a,c,e) is a Steiner triple system it is said to be perfect. In 2004, Küçükçifçi and Lindner had shown that there is a perfect hexagon triple system of order v if and only if and v≥7. In this paper, we investigate the existence of a perfect hexagon triple system with a given subsystem. We show that there exists a perfect hexagon triple system of order v with a perfect sub-hexagon triple system of order u if and only if v≥2u+1, and u≥7, which is a perfect hexagon triple system analogue of the Doyen–Wilson theorem.