A characterization for sparse -regular pairs.
A Characterization of 2-Tree Probe Interval Graphs
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 characterization of a class of graphs connected with the hysteresis phenomena
A characterization of geodetic graphs
A characterization of graphs in which some minimum dominating set covers all the edges
A characterization of -closed graphs
A characterization of middle graphs and a matroid associated with middle graphs of hypergraphs
A characterization of planar median graphs
Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
A characterization of the set of all shortest paths in a connected graph
Let be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in is defined as the set of all paths , then the lenght of does not exceed the length of . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...
A classification for maximal nonhamiltonian Burkard-Hammer graphs
A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is...
A classification of Ramanujan unitary Cayley graphs.
A family of nonregular distance monotone graphs
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
We characterize the class [...] L32 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 in the class of threshold graphs, where n is the number of vertices of a tested graph.
A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
A -factor containing a given Hamiltonian cycle.
A linear algorithm to recognize maximal generalized outerplanar graphs
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.
A new approach to chordal graphs
By a chordal graph is meant a graph with no induced cycle of length . By a ternary system is meant an ordered pair , where is a finite nonempty set, and . Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set , a bijective mapping from the set of all connected chordal graphs with onto the set of all ternary systems satisfying the axioms (A1)–(A5) is...
A New Characterization of Unichord-Free Graphs
Unichord-free graphs are defined as having no cycle with a unique chord. They have appeared in several papers recently and are also characterized by minimal separators always inducing edgeless subgraphs (in contrast to characterizing chordal graphs by minimal separators always inducing complete subgraphs). A new characterization of unichord-free graphs corresponds to a suitable reformulation of the standard simplicial vertex characterization of chordal graphs.
A new estimate for the vertex number of an edge-regular graph.
A note on another construction of graphs with vertices and cyclic automorphism group of order
The problem of finding minimal vertex number of graphs with a given automorphism group is addressed in this article for the case of cyclic groups. This problem was considered earlier by other authors. We give a construction of an undirected graph having vertices and automorphism group cyclic of order , . As a special case we get graphs with vertices and cyclic automorphism groups of order . It can revive interest in related problems.