Universal H-Colourable Graphs

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: for given m and n with m < n, m is adjacent to n if n has a 1 in the mth position of its binary expansion. It is well known that R is a universal graph in the set ${\mathcal{I}_c}$ of all countable graphs (since every graph in ${\mathcal{I}_c}$ is isomorphic to an induced subgraph of R) and that it is a homogeneous graph (since every isomorphism between two finite induced subgraphs of R extends to an automorphism of R). In this paper we construct a graph U(H) which is H-universal in → H _c , the induced-hereditary hom-property of H-colourable graphs consisting of all (countable) graphs which have a homomorphism into a given (countable) graph H. If H is the (finite) complete graph K _k , then → H _c is the property of k-colourable graphs. The universal graph U(H) is characterised by showing that it is, up to isomorphism, the unique denumerable, H-universal graph in → H _c which is H-homogeneous in → H _c . The graphs H for which ${U(H) \cong R}$ are also characterised. With small changes to the definitions, our results translate effortlessly to hold for digraphs too. Another slight adaptation of our work yields related results for (k, l)-split graphs.     

The set of irreducible graphs for the projective plane is finite

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K_{3, 3}. For positive integer n, let I_n (P) denote a smallest set of graphs whose maximal valency is n and such that any graph which does not embed in the real projective plane contains a subgraph homeomorphic to a graph in I_n (P) for some n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃ (P), and Glover and Huneke proved that I_n (P) is finite for all n. This note proves that I_n (P) is empty for all but a finite number of n. Hence there is a finite set of graphs for the projective plane analogous to Kuratowski's two graphs for the plane.     

Graphs with bounded valency that do not embed in the projective plane

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K₃₃. Let I_n(P) denote the minimal set of graphs whose vertices have miximal valency n such that any graph which does not embed in the real projective plane (or equivalently, does not embed in the Möbius band) contains a subgraph homeomorphic to a graph in I_n(P) for some positive integer n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃(P). This note proves that for each n, I_n(P) is finite.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

Universal graphs with a forbidden subgraph: Block path solidity

Let C be a finite connected graph for which there is a countable universal C-free graph, and whose tree of blocks is a path. Then the blocks of C are complete. This generalizes a result of Füredi and Komjáth, and fits naturally into a set of conjectures regarding the existence of countable C-free graphs, with C an arbitrary finite connected graph.     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

On a problem of R. Halin concerning infinite graphs II

For every countable, connected graph A containing no one-way infinite path the following is shown: Let G be an arbitrary graph which contains for every positive integer n a system of n disjoint graphs each isomorphic to a subdivision of A. Then G also contains infinitely many disjoint subgraphs each isomorphic to a subdivision of A. In addition, corrections of errors are given that occur unfortunately in the forerunner of the present paper.     

Arc-regular cubic graphs of order four times an odd integer

A graph is arc-regular if its automorphism group acts sharply-transitively on the set of its ordered edges. This paper answers an open question about the existence of arc-regular 3-valent graphs of order 4m where m is an odd integer. Using the Gorenstein?CWalter theorem, it is shown that any such graph must be a normal cover of a base graph, where the base graph has an arc-regular group of automorphisms that is isomorphic to a subgroup of Aut(PSL(2,q)) containing PSL(2,q) for some odd prime-power?q. Also a construction is given for infinitely many such graphs??namely a family of Cayley graphs for the groups PSL(2,p ³) where p is an odd prime; the smallest of these has order?9828.     

A note on power domination in grid graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs (see [T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, M.A. Henning, Power domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15(4) (2002) 519-529]). A set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph is its power domination number. In this paper, we determine the power domination number of an n×m grid graph.     

Intersection theory for graphs

An intersection theory developed by the author for matroids embedded in uniform geometries is applied to the case when the ambient geometry is the lattice of partitions of a finite set so that the matroid is a graph. General embedding theorems when applied to graphs give new interpretations to such invariants as the dichromate of Tutte. A polynomial in n + 1 variables, the polychromate, is defined for graphs with n vertices. This invariant is shown to be strictly stronger than the dichromate, it is edge-reconstructible and can be calculated for proper graphs from the polychromate of the complementary graph. By using Tutte's construction for codichromatic graphs (J. Combinatorial Theory 16 (1974), 168–174), copolychromatic (and therefore codichromatic) graphs of arbitrarily high connectivity are constructed thereby solving a problem posed in Tutte's paper.     

The topological dimension of limits of vertex replacements

Given an initial graph G, one may apply a rule R to G which replaces certain vertices of G with other graphs called replacement graphs to obtain a new graph R(G). By iterating this procedure, a sequence of graphs {Rn(G)} is obtained. When each graph in this sequence is normalized to have diameter one, the resulting sequence may converge in the Gromov-Hausdorff metric. In this paper, we compute the topological dimension of limit spaces of normalized sequences of iterated vertex replacements involving more than one replacement graph. We also give examples of vertex replacement rules that yield fractals.     

Dominating sets and domatic number of circular arc graphs

A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n∣E∣) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n² log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.