The forcing geodetic number of a graph

Gary Chartrand; Ping Zhang

Displaying similar documents to “The forcing geodetic number of a graph”

Extreme geodesic graphs

Gary Chartrand, Ping Zhang (2002)

Czechoslovak Mathematical Journal

Similarity:

For two vertices $u$ and $v$ of a graph $G$ , the closed interval $I [u, v]$ consists of $u$ , $v$ , and all vertices lying in some $u -- v$ geodesic of $G$ , while for $S \subseteq V (G)$ , the set $I [S]$ is the union of all sets $I [u, v]$ for $u, v \in S$ . A set $S$ of vertices of $G$ for which $I [S] = V (G)$ is a geodetic set for $G$ , and the minimum cardinality of a geodetic set is the geodetic number $g (G)$ . A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $e x (G)$ . A graph $G$ is an...

The all-paths transit function of a graph

Manoj Changat, Sandi Klavžar, Henry Martyn Mulder (2001)

Czechoslovak Mathematical Journal

Similarity:

A transit function $R$ on a set $V$ is a function $R V \times V \to 2^{V}$ satisfying the axioms $u \in R (u, v)$ , $R (u, v) = R (v, u)$ and $R (u, u) = {u}$ , for all $u, v \in V$ . The all-paths transit function of a connected graph is characterized by transit axioms.

An algebraic characterization of geodetic graphs

Ladislav Nebeský (1998)

Czechoslovak Mathematical Journal

Similarity:

We say that a binary operation $*$ is associated with a (finite undirected) graph $G$ (without loops and multiple edges) if $*$ is defined on $V (G)$ and $u v \in E (G)$ if and only if $u \neq v$ , $u * v = v$ and $v * u = u$ for any $u$ , $v \in V (G)$ . In the paper it is proved that a connected graph $G$ is geodetic if and only if there exists a binary operation associated with $G$ which fulfils a certain set of four axioms. (This characterization is obtained as an immediate consequence of a stronger result proved in the paper).

Containers and wide diameters of $P_{3} (G)$

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

Similarity:

The $P_{3}$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$ . Two vertices in $P_{3} (G)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$ -container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$ . The length of a container is the length of the longest path in it. The $w$ -wide diameter of $G$ is the minimum number $l$ such that there is a $w$ -container of length at most $l$ between any pair...

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.

The cobondage number of a graph

V.R. Kulli, B. Janakiram (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number $b_{c} (G)$ of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = X ⊆ V:|X| = 2 such that γ(G+X) < γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum...

On graphs with a unique minimum hull set

Gary Chartrand, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link $L (v_{i}) = G_{i}$ for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, $P_{r} (G)$ , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_{r}^{k} (G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_{r}^{k} (G)$ . The k-history $P_{r}^{- k} (H)$ is a subgraph of G that is induced by all edges that take part in the recursive...