Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterval-Like Graphs and Digraphs
146
0
0.0
(
0
)
Added by
Ross M. McConnell
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include, in addition to interval graphs, also adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing loops. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above example graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having all loops, or having a symmetric edge-set, or being bipartite. (For instance co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric.) We also offer some discussion of recognition algorithms and characterizations, saving the details for future papers.
rate research
Read More
Given a digraph $G$, a set $Xsubseteq V(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $Ssubseteq V(G)$ is said to be an independent set if no two vertices in $S$ are adjacent in $G$. A kernel (resp. solution) of $G$ is an independent and absorbing (resp. dominating) set in $G$. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph $G$ is an interval digraph if a pair of intervals $(S_u,T_u)$ can be assigned to each vertex $u$ of $G$ such that $(u,v)in E(G)$ if and only if $S_ucap T_v eqemptyset$. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs -- which arise when we require that the two intervals assigned to a vertex have to intersect. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs.
In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bipartite graph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.
A lower bound is obtained for the greatest possible number of colors in an interval colourings of some regular graphs.
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) geq 4n-2-p-q$. Later, he conjectured that if $n in mathbb{N}$, then $W(K_{2n}) = 4n - 2 - leftlfloorlog_2{n}rightrfloor - left | n_2 right |$, where $left | n_2 right |$ is the number of $1$s in the binary representation of $n$. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n leq 12$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
