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 geodetic number of median graphs

A set of vertices S in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from S. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.     

On the geodetic number and related metric sets in Cartesian product graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in at least one interval between the vertices of S. The size of a minimum geodetic set in G is the geodetic number of G. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors.     

A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs

Generalizing Cook and Pryce's construction procedures for geodetic blocks, an operation in geodetic graphs is discussed consisting of “pulling” a subgraph homeomorphic to a complete graph. This unifies and generalizes several of the known constructions of geodetic graphs.     

A forbidden subgraph characterization of line-polar bipartite graphs

A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6].     

The lower and upper forcing geodetic numbers of block–cactus graphs

A vertex set D in graph G is called a geodetic set if all vertices of G are lying on some shortest u–v path of G, where u, v ∈ D. The geodetic number of a graph G is the minimum cardinality among all geodetic sets. A subset S of a geodetic set D is called a forcing subset of D if D is the unique geodetic set containing S. The forcing geodetic number of D is the minimum cardinality of a forcing subset of D, and the lower and the upper forcing geodetic numbers of a graph G are the minimum and the maximum forcing geodetic numbers, respectively, among all minimum geodetic sets of G. In this paper, we find out the lower and the upper forcing geodetic numbers of block–cactus graphs.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.     

A class of geodetic blocks

A new class of geodetic blocks is constructed and it is shown how these are derived from Plesnik's geodetic homeomorphs of complete graphs.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

Remarks on Q-integral complete multipartite graphs

A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

Star-Uniform Graphs

A star-factor of a graph is a spanning subgraph each of whose components is a star. A graph G is called star-uniform if all star-factors of G have the same number of components. Motivated by the minimum cost spanning tree and the optimal assignment problems, Hartnell and Rall posed an open problem to characterize all the star-uniform graphs. In this paper, we show that a graph G is star-uniform if and only if G has equal domination and matching number. From this point of view, the star-uniform graphs were characterized by Randerath and Volkmann. Unfortunately, their characterization is incomplete. By deploying Gallai–Edmonds Matching Structure Theorem, we give a clear and complete characterization of star-unform 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.     

On a new reformulation of Hadwiger's conjecture

Assuming that every proper minor closed class of graphs contains a maximum with respect to the homomorphism order, we prove that such a maximum must be homomorphically equivalent to a complete graph. This proves that Hadwiger's conjecture is equivalent to saying that every minor closed class of graphs contains a maximum with respect to homomorphism order. Let F be a finite set of 2-connected graphs, and let C be the class of graphs with no minor from F. We prove that if C has a maximum, then any maximum of C must be homomorphically equivalent to a complete graph. This is a special case of a conjecture of Nešet?il and Ossona de Mendez.     

Weakly central-vertex complete graphs with applications to commutative rings

The zero-divisor graph of a commutative ring R is the graph whose vertices consist of the nonzero zero-divisors of R such that distinct vertices x and y are adjacent if and only if xy=0. In this paper, a decomposition theorem is provided to describe weakly central-vertex complete graphs of radius 1. This characterization is then applied to the class of zero-divisor graphs of commutative rings. For finite commutative rings whose zero-divisor graphs are not isomorphic to that of Z₄[X]/(X²), it is shown that weak central-vertex completeness is equivalent to the annihilator condition. Furthermore, a schema for describing zero-divisor graphs of radius 1 is provided.     

On graphs with a constant link,II

We study the following problem: For which finite graphs L do there exist graphs G such that the link (i.e., the neighborhood subgraph) of each vertex of G is isomorphic to L? We give a complete solution for the cases (i) L is a disjoint union of arcs, (ii) L is a tree with only one vertex of degree greater than two, (iii) L is a circle of prescribed length. Some other cases are also discussed. An interesting case is whether the situation is changed if we require G also to be finite. It transpires (see for example, Corollaries VII.3 and VII.4) that this is indeed the case.Part I of this paper will appear in [3]. It provides the basic definitions used in both part I and part II. Section III provides the basic tool, an identification procedure, that is used throughout the rest of the paper. Section IV sets up the basic building technique for the construction of more complicated graphs. It is shown how to build graphs such that the link of each vertex is an arc (of non-constant length), and how to control the proportional number of vertices with links of various lengths.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

Mutual exclusion scheduling with interval graphs or related classes, Part I

In this paper, the mutual exclusion scheduling problem is addressed. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93-109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the NP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.