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₃.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

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.     

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.     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Triangle path transit functions, betweenness and pseudo-modular graphs

The geodesic and induced path transit functions are the two well-studied interval functions in graphs. Two important transit functions related to the geodesic and induced path functions are the triangle path transit functions which consist of all vertices on all u,v-shortest (induced) paths or all vertices adjacent to two adjacent vertices on all u,v-shortest (induced) paths, for any two vertices u and v in a connected graph G. In this paper we study the two triangle path transit functions, namely the I^Δ and J^Δ on G. We discuss the betweenness axioms, for both triangle path transit functions. Also we present a characterization of pseudo-modular graphs using the transit function I^Δ by forbidden subgraphs.     

Distance-hereditary graphs

Distance-hereditary graphs (sensu Howorka) are connected graphs in which all induced paths are isometric. Examples of such graphs are provided by complete multipartite graphs and ptolemaic graphs. Every finite distance-hereditary graph is obtained from K₁ by iterating the following two operations: adding pendant vertices and splitting vertices. Moreover, distance-hereditary graphs are characterized in terms of the distance function d, or via forbidden isometric subgraphs.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

Graphs with a Minimal Number of Convex Sets

Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every u–v geodesic (i.e. shortest u–v path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced u–v path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

Graphs with 1-Hamiltonian-connected cubes

The cube G³ of a connected graph G is that graph having the same vertex set as G and in which two distinct vertices are adjacent if and only if their distance in G is at most three. A Hamiltonian-connected graph has the property that every two distinct vertices are joined by a Hamiltonian path. A graph G is 1-Hamiltonian-connected if, for every vertex w of G, the graphs G and G?w are Hamiltonian-connected. A characterization of graphs whose cubes are 1-Hamiltonian-connected is presented.     

On clique-critical graphs

A graph G is clique-critical if G and G?x have different clique-graphs for all vertices x of G. For any graph H, there is at most a finite number of different clique-critical graphs G such that H is the clique-graph of G. Upper and lower bounds for the number of vertices of the cliques of the critical graphs are obtained.     

Netlike partial cubes I. General properties

A set A of vertices of a graph G is C-convex if the vertex set of any cycle of the subgraph of G induced by the union of the intervals between each pair of elements of A is contained in A. A partial cube (isometric subgraph of a hypercube) is a netlike partial cube if, for each edge ab, the sets U_ab and U_ba are C-convex (U_ab being the set of all vertices closer to a than to b and adjacent to some vertices closer to b than to a, and vice versa for U_ba). Particular netlike partial cubes are median graphs, even cycles, benzenoid graphs and cellular bipartite graphs. In this paper we give different characterizations and properties of netlike partial cubes. In particular, as median graphs and cellular bipartite graphs, these graphs have a pre-hull number which is at most one, and moreover the convex hull of any isometric cycle of a netlike partial cube is, as in the case of bipartite cellular graphs, this cycle itself or, as in the case of median graphs, a hypercube. We also characterize the gated subgraphs of a netlike partial cube, and we show that the gated amalgam of two netlike partial cubes is a netlike partial cube.     

Cubic graphs without cut‐vertices having the same path layer matrix

The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1–4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut‐vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177–182, 2001     

Rainbow Connection in 3-Connected Graphs

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs.     

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.