Probabilistic Methods for Decomposition Dimension of Graphs

In a graph G, the distance from an edge e to a set FE(G) is the vertex distance from e to F in the line graph L(G). For a decomposition of E(G) into k sets, the distance vector of e is the k-tuple of distances from e to these sets. The decomposition dimension dec(G) of G is the smallest k such that G has a decomposition into k sets so that the distance vectors of the edges are distinct. For the complete graph K _n and the k-dimensional hypercube Q _k , we prove that (2–o(1))lgndec(K _n )(3.2+o(1))lgn and k/lgk dec(Q _k ) (3.17+o(1))k/lgk. The upper bounds use probabilistic methods directly or indirectly. We also prove that random graphs with edge probability p such that p n ^1– for some positive constant have decomposition dimension (lnn) with high probability. Acknowledgments.The authors thank Noga Alon for clarifying and strengthening the results in Sections 3 and 4. Thanks also go to a referee for repeated careful readings and suggestions.AMS classifications: 05C12, 05C35, 05D05, 05D40     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

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.     

Decomposition of Graphs into Chains

We establish a result on edge-disjoint paths with prescribedends in infinite trees and apply this to prove the conjectureof Eggleton and Skilton [1] that any connected graph has a decompositioninto chains such that at most one of these is one-way infiniteand each vertex is the end-vertex of at most one of the chainsand no vertex of infinite degree is such an end-vertex. We alsogive a necessary and sufficient condition for a graph to havea decomposition into one-way infinite chains.     

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.     

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.     

小波级数的Bouligand维数(英)

本文讨论小波级数的上、下Buoligangd维数，在小波级数满足一定的条件下，给出了与Weierstrass函数相应的结果．     

Grid Intersection Graphs and Order Dimension

We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.     

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.     

Metric Dimension and R-Sets of Connected Graphs

The R-set relative to a pair of distinct vertices of a connected graph G is the set of vertices whose distances to these vertices are distinct. This paper deduces some properties of R-sets of connected graphs. It is shown that for a connected graph G of order n and diameter 2 the number of R-sets equal to V(G) is bounded above by ?n²/4?{\lfloor n^{2}/4\rfloor} . It is conjectured that this bound holds for every connected graph of order n. A lower bound for the metric dimension dim(G) of G is proposed in terms of a family of R-sets of G having the property that every subfamily containing at least r ≥ 2 members has an empty intersection. Three sufficient conditions, which guarantee that a family F=(G_n)_{n 3 1}{\mathcal{F}=(G_{n})_{n\geq 1}} of graphs with unbounded order has unbounded metric dimension, are also proposed.     

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.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

图的树宽的分解定理

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

On the Metric Dimension of Imprimitive Distance-Regular Graphs

A resolving set for a graph \({\Gamma}\) is a collection of vertices S, chosen so that for each vertex v, the list of distances from v to the members of S uniquely specifies v. The metric dimension of \({\Gamma}\) is the smallest size of a resolving set for \({\Gamma}\). Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. We show how the metric dimension of an imprimitive distance-regular graph can be related to that of its halved and folded graphs. We also consider infinite families (including Taylor graphs and the incidence graphs of certain symmetric designs) where more precise results are possible.     

自仿函数分数阶导数的分形维数

研究一类自仿函数的分数阶导数,获得了自仿函数的Weyl-Marchaud分数阶导数的图像盒维数,证明了分数阶导数的阶与分形维数之间的线性关系.     

Dimension and Matchings in Comparability and Incomparability Graphs

We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the maximum matching in the cover graph of P has size \(O(\log d)\). On the other hand, there is a dual result in which the role of chains and antichains is reversed, as we show that there is also a matching of size d in the incomparability graph of P. The proof of the result for comparability graphs has elements in common with Perles’ proof of Dilworth’s theorem. Either result has the following theorem of Hiraguchi as an immediate corollary: \(\dim (P)\le |P|/2\) when |P|=4.     

Transitive Edge Coloring of Graphs and Dimension of Lattices

We explore properties of edge colorings of graphs dened by set intersections. An edge coloring of a graph G with vertex set V ={1,2, . . . , n} is called transitive if one can associate sets F ₁,F ₂, . . .,F _n to vertices of G so that for any two edges ij,kl E(G), the color of ij and kl is the same if and only if F _i F _j = F _k F _l . The term transitive refers to a natural partial order on the color set of these colorings.We prove a canonical Ramsey type result for transitive colorings of complete graphs which is equivalent to a stronger form of a conjecture of A. Sali on hypergraphs. This—through the reduction of Sali—shows that the dimension of n-element lattices is o(n) as conjectured by Füredi and Kahn.The proof relies on concepts and results which seem to have independent interest. One of them is a generalization of the induced matching lemma of Ruzsa and Szemerédi for transitive colorings. * Research supported in part by OTKA Grant T029074.     

Decomposition of Complete Graphs into Cycles and Stars

Let C _k denote a cycle of length k and let S _k denote a star with k edges. As usual K _n denotes the complete graph on n vertices. In this paper we investigate decomposition of K _n into C _l ’s and S _k ’s, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K _n into p copies of C ₄ and q copies of S ₄ if and only if ${4(p + q)={n \choose 2}, q\ne 1}$ if n is odd, and ${q\geq max\{3, \lceil{\frac{n}{4}\rceil}\}}$ if n is even.