On the sphericity and cubicity of graphs

The sphericity of a graph G is the smallest n such that the vertices in G can be mapped into unit-diameter spheres in n-space in such a way that two vertices are adjacent in G if and only if their assigned spheres intersect. The cubicity of G is defined similarly with unit cubes (edges parallel to the axes) used instead of unitdiameter spheres. In his study of molecular conformation, Havel (Ph.D. dissertation, Univ. of Calif., Berkeley, 1982) showed that there are finite graphs of sphericity 2 that have arbitrarily large cubicity, but he left open the question of whether there are graphs with sphericity greater than cubicity. It is shown here that such graphs exist for cubicity 2 or 3. The construction used to prove this generalizes to larger values for cubicity, but the proof technique does not. Hence it remains open whether there are graphs with large cubicities whose sphericities exceed their cubicities.     

Hypothesis of multisample sphericity

The hypothesis of multisample sphericity appears in different areas such as repeated measurement designs, checking the validity of F ratios in the analysis of variance problems, and testing circularity. This article deals with the modified likelihood ratio test for testing multisample sphericity, null and nonnull moments, as well as the null and nonnull distributions of the test statistic. Some approximations are also considered.Published in Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 136, pp. 153–161, 1984.     

The distribution of the sphericity test criterion

The exact distribution of Mauchly's sphericity test criterion W = |S|/[trS/p]^p, when S is the sum of product matrix from a sample of size N taken from a p-variate normal population, is obtained using contour integration and methods similar to those of Nair and Box. Tables of percentage points for p = 4(1)10, α = 0.01 and 0.05, and various values of N (including small) are given and comparisons made with approximate percentage points using methods of Box, Mauchly, Tukey and Wilks, and Davis.     

Geometric aspects of robust testing for normality and sphericity

Stochastic robustness of control systems under random excitation motivates challenging developments in geometric approach to robustness. The assumption of normality is rarely met when analyzing real data and thus the use of classic parametric methods with violated assumptions can result in the inaccurate computation of p-values, effect sizes, and confidence intervals. Therefore, quite naturally, research on robust testing for normality has become a new trend. Robust testing for normality can have counterintuitive behavior, some of the problems have been introduced in Stehlík et al. [Chemometrics and Intelligent Laboratory Systems 130 (2014 Stehlík, M., St?elec, L., and Thulin, M. 2014. On robust testing for normality in chemometrics. Chemometrics and Intelligent Laboratory Systems 130:98–108.[Crossref], [Web of Science ®] , [Google Scholar]): 98–108]. Here we concentrate on explanation of small-sample effects of normality testing and its robust properties, and embedding these questions into the more general question of testing for sphericity. We give geometric explanations for the critical tests. It turns out that the tests are robust against changes of the density generating function within the class of all continuous spherical sample distributions.     

On the sphericity testing of single source digraphs

A digraph D=(V,A) is called spherical, if it has an upward embedding on the round sphere which is an embedding of D on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, say to the north pole. It is easy to see that [S.M. Hashemi, Digraph embedding, Discrete Math. 233 (2001) 321-328] for upward embedding, plane and sphere are not equivalent, which is in contrast with the fact that they are equivalent for undirected graphs. On the other hand, it has been proved that sphericity testing for digraphs is an NP-complete problem [S.M. Hashemi, A. Kisielewicz, I. Rival, The complexity of upward drawings on spheres, Order 14 (1998) 327-363]. In this work we study sphericity testing of the single source digraphs. In particular, we shall present a polynomial time algorithm for sphericity testing of three connected single source digraphs.     

Universal graphs and induced-universal graphs

We construct graphs that contain all bounded-degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so-called universal graphs (or induced-universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced-universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced-universal graphs.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

Near-exact distributions for the independence and sphericity likelihood ratio test statistics

In this paper we show how, based on a decomposition of the likelihood ratio test for sphericity into two independent tests and a suitably developed decomposition of the characteristic function of the logarithm of the likelihood ratio test statistic to test independence in a set of variates, we may obtain extremely well-fitting near-exact distributions for both test statistics. Since both test statistics have the distribution of the product of independent Beta random variables, it is possible to obtain near-exact distributions for both statistics in the form of Generalized Near-Integer Gamma distributions or mixtures of these distributions. For the independence test statistic, numerical studies and comparisons with asymptotic distributions proposed by other authors show the extremely high accuracy of the near-exact distributions developed as approximations to the exact distribution. Concerning the sphericity test statistic, comparisons with formerly developed near-exact distributions show the advantages of these new near-exact distributions.     

Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Finite Euclidean graphs and Ramanujan graphs

We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221-238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167-185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum K(a,b;q). In particular, we always achieve , and in many (but not all) of the cases, instead of the well known . Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper.     

Some optimization problems with applications to canonical correlations and sphericity tests

Optimization problems are connected with maximization of three functions, namely, geometric mean, arithmetic mean and harmonic mean of the eigenvalues of (X′ΣX)^?1ΣY(Y′ΣY)^?1Y′ΣX, where Σ is positive definite, X and Y are p × r and p × s matrices of ranks r and s (≥r), respectively, and X′Y = 0. Some interpretations of these functions are given. It is shown that the maximum values of these functions are obtained at the same point given by X = (h₁ + ?₁h_p, …, h_r + ?_rh_p?r+1) and $\text{Y = (h}{}_1\text{? ?}{}_1\text{h}{}_{\mathrm{p}}\text{, …, h}{}_{\mathrm{r}}\text{? ?}{}_{\mathrm{r}}\text{h}{}_{\mathrm{p?r+1}}\text{,}\text{Y}{}_{\mathrm{r+1}}\text{, …,}\text{Y}{}_{\mathrm{s}}\text{)}$, where h₁, …, h_p are the eigenvectors of Σ corresponding to the eigenvalues λ₁ ≥ λ₂ ≥ … ≥ λ_p > 0, ?_j = +1 or ?1 for j = 1,2,…, r and $\text{Y}{}_{\mathrm{r+1}}\text{, …,}\text{Y}{}_{\mathrm{s}}$, are linear functions of h_r+1,…, h_p?r. These results are extended to intermediate stationary values. They are utilized in obtaining the inequalities for canonical correlations θ₁,…,θ_r and they are given by expressions (3.8)–(3.10). Further, some new union-intersection test procedures for testing the sphericity hypothesis are given through test statistics (3.11)–(3.13).     

The decompositions of line graphs,middle graphs and total graphs of complete graphs into forests

We construct decompositions of L(K_n), M(K_n) and T(K_n) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.     

Tests for sphericity under correlated multivariate regression equations model

Summary In this paper, the authors investigated the asymptotic distribution theory connected with the likelihood ratio test (LRT)-like test statistic for sphericity under correlated multivariate regression equations (CMRE) model. An asymptotic expression is obtained for the null distribution of the above test statistic. Asymptotic nonnull distribution of the above test statistic under fixed alternatives is also derived. The above results are derived when the underlying distribution is multivariate normal. It was also shown that the above results are valid even when the joint distribution of the observations is elliptically symmetric. The authors also derived the asymptotic null distribution of the LRT-like test statistic when the observations on each variable are elliptically symmetric. This work was supported by the Air Force Office of Scientific Research under Contract F49620-82-K-0001. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].