Results 1 to 10 of about 184,697 (198)
Reconstruction of interval graphs [PDF]
Theoretical Computer Science, 2009 AbstractThe graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs.
Masashi Kiyomi +2 more
openaire +2 more sources
Cleaning Interval Graphs [PDF]
Algorithmica, 2011 We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference |V(G)|-|V(H)|, with G and H being the larger and the smaller ...
Dániel Marx, Ildikó Schlotter
openaire +3 more sources
On the enumeration of interval graphs [PDF]
Proceedings of the American Mathematical Society, Series B, 2017 We present upper and lower bounds for the number i n i_n of interval graphs on n n vertices. Answering a question posed by Hanlon, we show that the ordinary generating function I ( x ) = ∑ n ≥ 0
Joyce C. Yang, Nicholas Pippenger
openaire +2 more sources
Closed graphs are proper interval graphs [PDF]
Analele Universitatii "Ovidius" Constanta - Seria Matematica, 2014 Abstract Let G be a connected simple graph. We prove that G is a closed graph if and only if G is a proper interval graph. As a consequence we obtain that there exist linear-time algorithms for closed graph recognition.
CRUPI, Marilena, RINALDO, GIANCARLO
openaire +6 more sources
On interval transmission irregular graphs [PDF]
Journal of Applied Mathematics and Computing, 2021 19pp, 15 ...
Salem Al-Yakoob, Dragan Stevanović
openaire +3 more sources
Open-interval graphs versus closed-interval graphs
Discrete Mathematics, 1987 AbstractA graph G = (V, E) is said to be represented by a family F of nonempty sets if there is a bijection f: V → F such that uv ϵ E if and only if f(u)∩f(v) ≠ Ø. It is proved that if G is a Countable graph then G can be represented by open intervals on the real line if and only if G can be represented by closed intervals on the real line, however ...
Hiroshi Maehara, Peter Frankl
openaire +2 more sources
Simultaneous Interval Graphs [PDF]
, 2010 In a recent paper, we introduced the simultaneous representation problem (defined for any graph class C) and studied the problem for chordal, comparability and permutation graphs. For interval graphs, the problem is defined as follows. Two interval graphs G_1 and G_2, sharing some vertices I (and the corresponding induced edges), are said to be ...
Krishnam Raju Jampani, Anna Lubiw
openaire +3 more sources
Discrete Applied Mathematics, 1998 AbstractProbe interval graphs have been introduced in the physical mapping and sequencing of DNA as a generalization of interval graphs. We prove that probe interval graphs are weakly triangulated, and hence are perfect, and characterize probe interval graphs by consecutive orders of their intrinsic cliques.
Peisen Zhang, Chi Wang, Fred R. McMorris
openaire +2 more sources
Discrete Mathematics, 1985 AbstractThe interval thickness of a graph G is the minimum clique number over any interval supergraph of G. The node-search number is the least number of searchers required to clear the ‘contaminated’ edges of a graph. The clearing is accomplished by concurrently having searchers on both of its endpoints.We prove that for any graph, these two ...
Lefteris M. Kirousis +3 more
openaire +2 more sources