An algebraic characterization of geodetic graphs

Ladislav Nebeský

Displaying similar documents to “An algebraic characterization of geodetic graphs”

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair $(X_{0}, T_{0})$ , where $X_{0}$ is a finite nonempty set and $T_{0}$ is a ternary relation on $X_{0}$ . By the underlying graph of a ternary structure $(X_{0}, T_{0})$ we mean the (undirected) graph $G$ with the properties that $X_{0}$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if ${x \in X_{0} T_{0} (u, x, v)} \cup {x \in X_{0} T_{0} (v, x, u)} = {u, v} .$ A ternary structure $(X_{0}, T_{0})$ is said to be the B-structure of a connected graph $G$ if $X_{0}$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_{0}$ : $T_{0} (x, u, y)$ if and only if $u$ belongs to an...

A tree as a finite nonempty set with a binary operation

Ladislav Nebeský (2000)

Mathematica Bohemica

Similarity:

A (finite) acyclic connected graph is called a tree. Let $W$ be a finite nonempty set, and let $H (W)$ be the set of all trees $T$ with the property that $W$ is the vertex set of $T$ . We will find a one-to-one correspondence between $H (W)$ and the set of all binary operations on $W$ which satisfy a certain set of three axioms (stated in this note).

A new approach to chordal graphs

Ladislav Nebeský (2007)

Czechoslovak Mathematical Journal

Similarity:

By a chordal graph is meant a graph with no induced cycle of length $\geq 4$ . By a ternary system is meant an ordered pair $(W, T)$ , where $W$ is a finite nonempty set, and $T \subseteq W \times W \times W$ . 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 $W$ , a bijective mapping from the set of all connected chordal graphs $G$ with $V (G) = W$ onto the set of all ternary systems $(W, T)$ satisfying the axioms (A1)–(A5)...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.