All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 84

Showing per page

A Characterization of 2-Tree Probe Interval Graphs

David E. Brown, Breeann M. Flesch, J. Richard (2014)

Discussiones Mathematicae Graph Theory

A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150...

A co-ideal based identity-summand graph of a commutative semiring

S. Ebrahimi Atani, S. Dolati Pish Hesari, M. Khoramdel (2015)

Commentationes Mathematicae Universitatis Carolinae

Let I be a strong co-ideal of a commutative semiring R with identity. Let Γ I ( R ) be a graph with the set of vertices S I ( R ) = { x ∈ R ∖ I : x + y ∈ I for some y ∈ R ∖ I } , where two distinct vertices x and y are adjacent if and only if x + y ∈ I . We look at the diameter and girth of this graph. Also we discuss when Γ I ( R ) is bipartite. Moreover, studies are done on the planarity, clique, and chromatic number of this graph. Examples illustrating the results are presented.

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

Automata-based representations for infinite graphs

Salvatore La Torre, Margherita Napoli (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...

Automata-based Representations for Infinite Graphs

Salvatore La Torre, Margherita Napoli (2010)

RAIRO - Theoretical Informatics and Applications

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and...

Clique graph representations of ptolemaic graphs

Terry A. Mckee (2010)

Discussiones Mathematicae Graph Theory

A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special...

Coloring rectangular blocks in 3-space

Colton Magnant, Daniel M. Martin (2011)

Discussiones Mathematicae Graph Theory

If rooms in an office building are allowed to be any rectangular solid, how many colors does it take to paint any configuration of rooms so that no two rooms sharing a wall or ceiling/floor get the same color? In this work, we provide a new construction which shows this number can be arbitrarily large.

Currently displaying 1 – 20 of 84

Page 1 Next