On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.     

A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs

Two-sample hypothesis testing for random graphs arises naturally in neuroscience, social networks, and machine learning. In this article, we consider a semiparametric problem of two-sample hypothesis testing for a class of latent position random graphs. We formulate a notion of consistency in this context and propose a valid test for the hypothesis that two finite-dimensional random dot product graphs on a common vertex set have the same generating latent positions or have generating latent positions that are scaled or diagonal transformations of one another. Our test statistic is a function of a spectral decomposition of the adjacency matrix for each graph and our test procedure is consistent across a broad range of alternatives. We apply our test procedure to real biological data: in a test-retest dataset of neural connectome graphs, we are able to distinguish between scans from different subjects; and in the C. elegans connectome, we are able to distinguish between chemical and electrical networks. The latter example is a concrete demonstration that our test can have power even for small-sample sizes. We conclude by discussing the relationship between our test procedure and generalized likelihood ratio tests. Supplementary materials for this article are available online.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

几类可升分解的图

Ａｌａｖｉ等人在文献［１］中定义了图的一种新分解，即“升分解”，并且猜想：任意有正数条边的图都可升分解。本文证明了下面三类图可升分解，并得到了一些有意义的推论。１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ≥５）；２对称图可升分解；３对称图Ｇ的混合积（Ｇ；ｋ）可升分解。     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

Retracts of Products of Chordal Graphs

In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K_{2, 3}, the 4‐wheel minus one spoke , and the k‐wheels (for as induced subgraphs. We also show that these graphs G are exactly the cage‐amalgamation graphs as introduced by Bre?ar and Tepeh Horvat (Cage‐amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071–1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1‐skeletons of CAT(0) cubical complexes. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 161–180, 2013     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

Subdirect Decomposition of n-Chromatic Graphs

It is shown that any n-chromatic graph is a full subdirect product of copies of the complete graphs K _n and K _n+1, except for some easily described graphs which are full subdirect products of copies of K _n+1 - {°-°} and K _n+2 - {°-°}; full means here that the projections of the decomposition are epimorphic in edges. This improves some results of Sabidussi. Subdirect powers of K _n or K _n+1 - {°-°} are also characterized, and the subdirectly irreducibles of the quasivariety of n -colorable graphs with respect to full and ordinary decompositions are determined.     

On the Acyclic Chromatic Number of Hamming Graphs

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given. Gretchen L. Matthews: The work of this author is supported by NSA H-98230-06-1-0008.     

边值问题的概率数值方法

该文运用概率理论研究了一种有界和无界区域上边值问题的数值方法.其主要思想如下: 先写出所求边值问题解的随机表达方式, 再构造一个辅助球, 并且通过区域边界上的剖分将问题离散化,最后利用漂移布朗族的强马尔可夫性和它的球面首中时、首中位置的分布, 获得离散问题的解.     

图的树宽的分解定理

图的树宽问题是名的ＮＰ－困难问题。其分解原则在确定树宽的一般算法和特殊算法中有重要应用。本给出这方面的若干定理。     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

笛卡尔乘积图的成对控制

Let γpr（G） denote the paired domination number and G □ H denote the Cartesian product of graphs G and H. In this paper we show that for all graphs G and H without isolated vertex, γpr（G）γpr（H）≤ 7γpr （G □H）.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Probabilistic norms and convergence of random variables

We prove that the probabilistic norms of suitable Probabilistic Normed spaces induce convergence in probability, L^p convergence and almost sure convergence.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

Probabilistic Analysis of Galerkin-Like Methods for the Fredholm Equation of the Second Kind

1.IntroductionQuantitativeprobabilisticanalysiswascarriedoutforseveralnumericalproblems.Forasystematicsurvey,werefertoTraubetal.(1988)andreferencestherein.Smale(1985)gavethefirstquantitativeanalysisforconcretemeasure.Heexpectedthattheapproachtheremightleadtoamoresystematicwayofanalysingforthecostofnumericalalgorithms.Heinrich(1991)continuedthislineandgavethefirstquantitativeanalysisforconcretemeasuresandalgorithmsforintegralequationofthesecondkind.There,theanalysiswascarriedoutfortheGalerkin…     

图的最小填充的分解定理

在计算数学领域,稀疏矩阵的最小填充排序问题由于其重要的实际意义而受到重视。本文从图论的观点提出一种处理方法,即运用分解定理来处理一些特殊结构,从而导出一些特殊图的最小填充数。     

高维Dirchlet问题数值解的概率方法

本文用概率方法求得高维Dirichlet内问题和外问题在一般区域上的数值解.高维漂移布朗族对停时具有强马氏性,它在球面上的击中时和位置分布已知,再利用Dirichlet问题解的随机表达式,我们可以获得高维Dirichlet问题的数值解.