A theorem on the maximum number of disjoint steiner triple systems

We prove that D(2v + 1) ? v + 1 + D(v) for v > 3 where D(v) denotes the maximum number of pairwise disjoint Steiner triple systems of order v. Since D(v) ? v ? 2 it follows that for v > 3, D(2v + 1) = 2v ?1 whenever D(v) = v ? 2.     

On large sets of disjoint steiner triple systems I

Let D(v) denote the maximum number of pairwise disjoint Steiner triple systems of order v. In this paper, it is proved that if D(2 + n) = n, p is a prime number, p ≡ 7 (mod 8) or p? {5, 17, 19, 2}, and (p, n) ≠ (5, 1), then D(2 + pn) = pn.     

On large sets of disjoint Steiner triple systems II

Let D(v) denote the maximum number of pairwise disjoint Steiner triple systems of order v. In this paper, we prove that if n is an odd number, there exist 12 mutually orthogonal Latin squares of order n and D(1 + 2n) = 2n ? 1, then D(1 + 12n) = 12n ? 1.     

On the maximum number of disjoint Steiner triple systems

Let D(v) be the maximum number of pairwise disjoint Steiner triple systems of order v. We prove that D(3v)≥2v+D(v) for every v ≡ 1 or 3 (mod 6), v≥3. As a corollary, we have D(3ⁿ)=3ⁿ-2 for every n≥1.     

Large sets of extended directed triple systems with odd orders

For three types of triples, unordered, cyclic and transitive, the corresponding extended triple, extended triple system and their large set are introduced. The spectrum of LEDTS(v) for even v has been given in our paper (Liu and Kang (2009) [9]). In this paper, we shall discuss the existence problem of LEDTS(v) for odd v and give the almost complete conclusion: there exists an LEDTS(v) for any positive integer v≠4 except possible v=95,143,167,203,215.     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

Volume mean densities for the heat equation

It is shown that, for solid caps D of heat balls in ? ^{d + 1} with center z ₀ = (0, 0), there exist Borel measurable functions w on D such that inf w(D) > 0 and ∫ v(z)w(z) dz ≤ v(z ₀), for every supertemperature v on a neighborhood of D?. This disproves a conjecture by N. Suzuki and N.A. Watson. On the other hand, it turns out that there is no such volume mean density, if the bounded domain D in ? ^d × (?∞, 0) is only slightly wider at z ₀ than a heat ball.     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.     

Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Lower and upper orientable strong radius and strong diameter of complete k-partite graphs

For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

Diagonal norm hermitian matrices

If v is a norm on $\text{C}$ⁿ, let H(v) denote the set of all norm-Hermitians in $\text{C}$ⁿⁿ. Let S be a subset of the set of real diagonal matrices D. Then there exists a norm v such that S=H(v) (or S = H(v)∩D) if and only if S contains the identity and S is a subspace of D with a basis consisting of rational vectors. As a corollary, it is shown that, for a diagonable matrix h with distinct eigenvalues λ₁,…, λ_r, r?n, there is a norm v such that h ∈ H(v), but h^s?H(v), for some integer s, if and only if λ₂–λ₁,…, λ_r–λ₁ are linearly dependent over the rationals. It is also shown that the set of all norms v, for which H(v) consists of all real multiples of the identity, is an open, dense subset, in a natural metric, of the set of all norms.     

A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph

The notion of a competition graph was introduced by Cohen in 1968. The competition graph C(D) of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.     

The vertex linear arboricity of distance graphs

A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,v∈R are adjacent if and only if |u-v|∈D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and δ. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.     

On a cyclic connectivity property of directed graphs

Let us call a digraph D cycle-connected if for every pair of vertices u,v∈V(D) there exists a cycle containing both u and v. In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge e∈E(D) such that for every w∈V(D) there exists a cycle C such that w∈V(C) and e∈E(C)?In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].