Search

Given a set system (also well-known as a hypergraph) H = {U, X}, where U is a set of elements and X is a set of subsets of U, an exact hitting set S is a subset of U such that each subset in X contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as Exactly Hittable Interval Graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG. [ABSTRACT FROM AUTHOR]

A graph G is weighted–k–list–antimagic if for any vertex weighting ω: V (G) → R and any list assignment L: E(G) → 2R with |L(e)| ≥ |E(G)| + k there exists an edge labeling f such that f(e) ∈ L(e) for all e ∈ E(G), labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on n vertices having no K1 or K2 component is weighted–[ 4n/3 ] –list–antimagic. [ABSTRACT FROM AUTHOR]

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic. [ABSTRACT FROM AUTHOR]

A graph is a probe interval graph if its vertices can be partitioned into probes and nonprobes with an interval associated to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is a probe. A graph G = (V,E) is a tolerance graph if each vertex v ∈ V can be associated to an interval Iv of the real line and a positive real number tv such that uv ∈ E if and only if |Iu ∩ Iv| ≥ min {tu; tv}. In this paper we present O(|V| + |E|) recognition algorithms for both bipartite probe interval graphs and bipartite tolerance graphs. We also give a new structural characterization for each class which follows from the algorithms. [ABSTRACT FROM AUTHOR]

For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpiński graphs. [ABSTRACT FROM AUTHOR]

Several matrices can be associated to a graph such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question "Which graphs are determined by their spectrum?" remains a difficult problem in algebraic graph theory. In this article we enlarge the known families of graphs determined by their spectrum by considering some unicyclic graphs. An odd (resp. even) sun is a graph obtained by appending a pendant vertex to each vertex of an odd (resp. even) cycle. A broken sun is a graph obtained by deleting pendant vertices of a sun. In this paper we prove that a sun is determined by its Laplacian spectrum, an odd sun is determined by its adjacency spectrum (counter-examples are given for even suns) and we give some spectral characterizations of broken suns. [ABSTRACT FROM AUTHOR]

Let G be a graph on vertices v[sub1], v[sub2],..., v[subn]. The b-chromatic number of G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i ≤ k, has at least one representant x[subi] adjacent to a vertex of every color j, 1 ≤ j ≠ i ≤ k. In this paper, we give the exact value for the b-chromatic number of power graphs of a path and we determine bounds for the b-chromatic number of power graphs of a cycle. [ABSTRACT FROM AUTHOR]