2-3 graphs which have Vizing's adjacency property.
3-consecutive c-colorings of graphs
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with for k = 3 and k = 4.
4-cycle properties for characterizing rectagraphs and hypercubes
A -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free -graph. -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in -graphs and more specifically in -graphs,...
4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs
Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u, v ∈ V (D), the existence of a uv-directed path of length k in D implies that (u, v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and...
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.