Isometric embedding in products of complete graphs

An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers 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.     

Excess in critical graphs

In this paper we prove that the cartesian product of two trees is a semistable graph and we exhibit several vertices of semistability. We show that in most cases the cartesian product of two paths is completely semistable and we list the exceptions. Finally, we characterize stable composite graphs.     

On the hierarchical product of graphs and the generalized binomial tree

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties.     

Distance-residual subgraphs

For a connected finite graph G and a subset V₀ of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from V₀. Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored.     

The non-nilpotent graph of a semigroup

We associate a graph ${\mathcal{N}}_{S}$ with a semigroup S (called the upper non-nilpotent graph of S). The vertices of this graph are the elements of S and two vertices are adjacent if they generate a semigroup that is not nilpotent (in the sense of Malcev). In case S is a group this graph has been introduced by A. Abdollahi and M.?Zarrin and some remarkable properties have been proved. The aim of this paper is to study this graph (and some related graphs, such as the non-commuting graph) and to discover the algebraic structure of S determined by the associated graph. It is shown that if a finite semigroup S has empty upper non-nilpotent graph then S is positively Engel. On the other hand, a semigroup has a complete upper non-nilpotent graph if and only if it is a completely simple semigroup that is a band. One of the main results states that if all connected ${\mathcal{N}}_{S}$ -components of a semigroup S are complete (with at least two elements) then S is a band that is a semilattice of its connected components and, moreover, S is an iterated total ideal extension of its connected components. We also show that some graphs, such as a cycle C _n on n vertices (with n??5), are not the upper non-nilpotent graph of a semigroup. Also, there is precisely one graph on 4 vertices that is not the upper non-nilpotent graph of a semigroup with 4 elements. This work also is a continuation of earlier work by Okni??ski, Riley and the first named author on (Malcev) nilpotent semigroups.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Hom complexes and homotopy in the category of graphs

In this extended abstract we develop a notion of ×-homotopy of graph maps that is based on the internal hom associated to the categorical product. We show that graph ×-homotopy is characterized by the topological properties of the so-called Hom complex, a functorial way to assign a poset to a pair of graphs. Along the way we establish some structural properties of Hom complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. We end with a discussion of graph homotopies arising from other internal homs, including the construction of ‘A-theory’ associated to the cartesian product in the category of reflexive graphs. For proofs and further discussions we refer the reader to the full paper [Anton Dochtermann. Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275].     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

On Partitional and Other Related Graphs

The partitional graphs, which are a subclass of the sequential graphs, were recently introduced by Ichishima and Oshima (Math Comput Sci 3:39–45, 2010), and the cartesian product of a partitional graph and K ₂ was shown to be partitional, sequential, harmonious and felicitous. In this paper, we present some necessary conditions for a graph to be partitional. By means of these, we study the partitional properties of certain classes of graphs. In particular, we completely characterize the classes of the graphs B _m and K _m,2 × Q _n that are partitional. We also establish the relationships between partitional graphs and graphs with strong α-valuations as well as strongly felicitous graphs.     

Recognition of characteristically simple group <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> × <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> by character degree graph and order

The character degree graph of a finite group G is the graph whose vertices are the prime divisors of the irreducible character degrees of G and two vertices p and q are joined by an edge if pq divides some irreducible character degree of G. It is proved that some simple groups are uniquely determined by their orders and their character degree graphs. But since the character degree graphs of the characteristically simple groups are complete, there are very narrow class of characteristically simple groups which are characterizable by this method.We prove that the characteristically simple group A₅ × A₅ is uniquely determined by its order and its character degree graph. We note that this is the first example of a non simple group which is determined by order and character degree graph. As a consequence of our result we conclude that A₅ × A₅ is uniquely determined by its complex group algebra.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Obstructions to chordal circular-arc graphs of small independence number

A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree.     

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.     

Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.     

On Partitional Labelings of Graphs

The notion of partitional graphs, a subclass of sequential graphs, is introduced, and the cartesian product of a partitional graph and K ₂ is shown to be partitional. Every sequential graph is harmonious and felicitous. The partitional property of some bipartite graphs including the n-dimensional cube Q _n is studied, and thus this paper extends what was known about the sequentialness, harmoniousness and felicitousness of such graphs.     

The number of spanning trees of plane graphs with reflective symmetry

A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G.