Chromaticity of two-trees

The graphs called 2-trees are defined by recursion. The smallest 2-tree is the complete graph on 2 vertices. A 2-tree on n + 1 vertices (where n ≥ 2) is obtained by adding a new vertex adjacent to each of 2 arbitrarily selected adjacent vertices in a 2-tree on n vertices. A graph G is a 2-tree on n(≥2) vertices if and only if its chromatic polynomial is equal to γ(γ - 1)(γ - 2)^n—2.     

On the Structure of Contractible Edges in <Emphasis Type="Italic">k</Emphasis>-connected Partial <Emphasis Type="Italic">k</Emphasis>-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

Scale Free Properties of Random <Emphasis Type="Italic">k</Emphasis>-Trees

Scale free graphs have attracted attention as their non-uniform structure that can be used as a model for many social networks including the WWW and the Internet. In this paper, we propose a simple random model for generating scale free k-trees. For any fixed integer k, a k-tree consists of a generalized tree parameterized by k, and is one of the basic notions in the area of graph minors. Our model is quite simple and natural; it first picks a maximal clique of size k + 1 uniformly at random, it then picks k vertices in the clique uniformly at random, and adds a new vertex incident to the k vertices. That is, the model only makes uniform random choices twice per vertex. Then (asymptotically) the distribution of vertex degree in the resultant k-tree follows a power law with exponent 2 + 1/k, the k-tree has a large clustering coefficient, and the diameter is small. Moreover, our experimental results indicate that the resultant k-trees have extremely small diameter, proportional to o(log n), where n is the number of vertices in the k-tree, and the o(1) term is a function of k.     

Subclasses of k-trees: Characterization and recognition

A k-tree is either a complete graph on k vertices or a graph G=(V,E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees.     

On the asymptotic behavior of the independence number of a random (n,n)-tree

An (r, s)-tree is a connected, acyclic, bipartite graph withr light ands dark vertices. Uniform probability is assigned to the space,(r, s), of (r, s)-trees. In this paper, we apply the probabilistic method to determine bounds for the vertex and the edge independence numbers for almost all (n, n)-trees in(n,n). Consequently, we find that for almost all (n, n)-trees the percentage of dark vertices in a maximum matching is at least 72%.First author supported in part by grants from TGRC-KOSEF and BSRI 1409.     

Separating subgraphs in k-trees: Cables and caterpillars

The class of k-trees has the property that the minimal sets of vertices separating two nonadjacent vertices u and v of a k-tree Q induce k-complete subgraphs. We show that the union T of these subgraphs belongs to a subclass of (k ? 1)-trees which generalizes caterpillars. The maximum order of a monochromatic set of vertices in the optimal coloring of this (k ? 1)-tree T determines the length of the minimal collection of k vertex-disjoint paths between the two vertices of Q, the u, v-cable, which is spanned on all vertices of T.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

Degree sets ofk-trees: Smallk

Ak-tree is ak-uniform hypergraph constructed from a single edge by the successive addition of edges each containing a new vertex andk−1 vertices of an existing edge. We show that ifD is any finite set of positive integers which includes 1, thenD is the set of vertex degrees of somek-tree fork=2, 3, and 4, and that there is precisely one such set,D={1, 4, 6}, which is not the set of degrees of any 5-tree. We also show for eachk≧2 that such a setD is the set of degrees of somek-tree provided only thatD contains some elementd which satisfiesd≧k (k−1)−2 [k/2]+3.     

On simplices in diameter graphs in ℝ4

Agraph G is a diameter graph in ?^d if its vertex set is a finite subset in ?^d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in ?⁴ contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in ?⁴, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

     

Packing Trees with Constraints on the Leaf Degree

If m is a positive integer then we call a tree on at least 2 vertices an m-tree if no vertex is adjacent to more than m leaves. Kaneko proved that a connected, undirected graph G = (V, E) has a spanning m-tree if and only if for every the number of isolated vertices of G − X is at most —unless we have the exceptional case of and m = 1. As an attempt to integrate this result into the theory of graph packings, in this paper we consider the problem of packing a graph with m-trees. We use an approach different from that of Kaneko, and we deduce Gallai–Edmonds and Berge–Tutte type theorems and a matroidal result for the m-tree packing problem. Jácint Szabó: Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No.504438.     

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability.     

The graphs for which the maximum multiplicity of an eigenvalue is two

Characterized are all simple undirected graphs G such that any real symmetric matrix that has graph G has no eigenvalues of multiplicity more than 2. All such graphs are partial 2-trees (and this follows from a result for rather general fields), but only certain partial 2-trees guarantee maximum multiplicity 2. Among partial linear 2-trees, they are only those whose vertices can be covered by two ‘parallel’ induced paths. The remaining graphs that guarantee maximum multiplicity 2 are composed of certain identified families of ‘exceptional’ partial 2-trees that are not linear.     

Vertex‐pancyclicity of hypertournaments

A hypertournament or a k‐tournament, on n vertices, 2≤k≤n, is a pair T=(V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles can be found through any vertex. A k‐tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. A question posed by Gutin and Yeo about the characterization of pancyclic and vertex‐pancyclic hypertournaments is examined in this article. We extend Moon's Theorem for tournaments to hypertournaments. We prove that if k≥8 and n≥k + 3, then a k‐tournament on n vertices is vertex‐pancyclic if and only if it is strong. Similar results hold for other values of k. We also show that when n≥7, k≥4, and n≥k + 2, a strong k‐tournament on n vertices is pancyclic if and only if it is strong. The bound n≥k+ 2 is tight. We also find bounds for the generalized problem when we extend vertex‐pancyclicity to require d edge‐disjoint cycles of each possible length and extend strong connectivity to require d edge‐disjoint paths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 338–348, 2010     

Half-Transitive Graphs of Prime-Cube Order

We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p ³ and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p ³ and exponent p ², and up to isomorphism there are exactly (p – 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.     

Realizability of Graphs

A graph is d-realizable if, for every configuration of its vertices in E^N, there exists a another corresponding configuration in E^d with the same edge lengths. A graph is 2-realizable if and only if it is a partial 2-tree, i.e., a subgraph of the 2-sum of triangles in the sense of graph theory. We show that a graph is 3-realizable if and only if it does not have K₅ or the 1-skeleton of the octahedron as a minor.     

On Urysohn’s ℝ-Tree

In the short note of 1927, Urysohn constructed the metric space R that is nowhere locally separable. There is no publication with indications that R is a (noncomplete) ?-tree that has valency c at each point. The author in 1989, as well as Polterovich and Shnirelman in 1997, constructed ?-trees isometric to R unaware of the paper by Urysohn. In this paper the author considers various constructions of the ?-tree R and of the minimal complete ?-tree of valency c including R, as well as the characterizations of ?-trees, their properties, and connections with ultrametric spaces.

     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

Drawing planar 3-trees with given face areas

We study straight-line drawings of planar graphs such that each interior face has a prescribed area. It was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face areas are rational, and we can bound the resolution. We also give some negative results for other graph classes.     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.