Page 1 Next

## Displaying 1 – 20 of 376

Showing per page

### 2-3 graphs which have Vizing's adjacency property.

Aequationes mathematicae

### 3-consecutive c-colorings of graphs

Discussiones Mathematicae Graph Theory

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 ${\left(\chi ̅\right)}_{3CC}\left(G\right)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ${\left(\chi ̅\right)}_{3CC}\left(G\right)\ge k$ for k = 3 and k = 4.

### 4-cycle properties for characterizing rectagraphs and hypercubes

Czechoslovak Mathematical Journal

A $\left(0,2\right)$-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $\left(0,\lambda \right)$-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $\left(0,2\right)$-graph. $\left(0,2\right)$-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 $\left(0,\lambda \right)$-graphs and more specifically in $\left(0,2\right)$-graphs,...

### 4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs

Discussiones Mathematicae Graph Theory

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 $\epsilon$-regular pairs.

The Electronic Journal of Combinatorics [electronic only]

### A Characterization of 2-Tree Probe Interval Graphs

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 characterization of a class of graphs connected with the hysteresis phenomena

Proceedings of the 10th Winter School on Abstract Analysis

### A characterization of geodetic graphs

Czechoslovak Mathematical Journal

### A characterization of graphs in which some minimum dominating set covers all the edges

Czechoslovak Mathematical Journal

### A characterization of ${K}_{r,s}$-closed graphs

Mathematica Slovaca

### A characterization of middle graphs and a matroid associated with middle graphs of hypergraphs

Fundamenta Mathematicae

### A characterization of planar median graphs

Discussiones Mathematicae Graph Theory

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

Mathematica Bohemica

Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $ℒ$ of all shortest paths in $G$ is defined as the set of all paths $\xi$, then the lenght of $\xi$ does not exceed the length of $\varsigma$. 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

Discussiones Mathematicae Graph Theory

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.

The Electronic Journal of Combinatorics [electronic only]

### A family of nonregular distance monotone graphs

Czechoslovak Mathematical Journal

### 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

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.

### A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs

Czechoslovak Mathematical Journal

### A $\left[k,k+1\right]$-factor containing a given Hamiltonian cycle.

The Electronic Journal of Combinatorics [electronic only]

### A linear algorithm to recognize maximal generalized outerplanar graphs

Mathematica Bohemica

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.

Page 1 Next