All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 26 Next

Displaying 501 – 520 of 561

Showing per page

Transitive closure and transitive reduction in bidirected graphs

Ouahiba Bessouf, Abdelkader Khelladi, Thomas Zaslavsky (2019)

Czechoslovak Mathematical Journal

In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.

Travel groupoids

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

In this paper, by a travel groupoid is meant an ordered pair ( V , * ) such that V is a nonempty set and * is a binary operation on V satisfying the following two conditions for all u , v ∈ V : ( u * v ) * u = u ; if ( u * v ) * v = u , then u = v . Let ( V , * ) be a travel groupoid. It is easy to show that if x , y ∈ V , then x * y = y if and only if y * x = x . We say that ( V , * ) is on a (finite or infinite) graph G if V ( G ) = V and E ( G ) = { { u , v } u , v ∈ V and u ≠ u * v = v } . Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.

Travel groupoids on infinite graphs

Jung Rae Cho, Jeongmi Park, Yoshio Sano (2014)

Czechoslovak Mathematical Journal

The notion of travel groupoids was introduced by L. Nebeský in 2006 in connection with a study on geodetic graphs. A travel groupoid is a pair of a set V and a binary operation * on V satisfying two axioms. We can associate a graph with a travel groupoid. We say that a graph G has a travel groupoid if the graph associated with the travel groupoid is equal to G . Nebeský gave a characterization of finite graphs having a travel groupoid. In this paper, we study travel groupoids on infinite graphs....

Tree compression pushdown automaton

Jan Janoušek, Bořivoj Melichar, Martin Poliak (2012)

Kybernetika

A new kind of a deterministic pushdown automaton, called a Tree Compression Automaton, is presented. The tree compression automaton represents a complete compressed index of a set of trees for subtrees and accepts all subtrees of given trees. The algorithm for constructing our pushdown automaton is incremental. For a single tree with n nodes, the automaton has at most n + 1 states, its transition function cardinality is at most 4 n and there are 2 n + 1 pushdown store symbols. If hashing is used for storing...

Tree-like isometric subgraphs of hypercubes

Bostjan Brešar, Wilfried Imrich, Sandi Klavžar (2003)

Discussiones Mathematicae Graph Theory

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like...

Tree-Like Partial Hamming Graphs

Tanja Gologranc (2014)

Discussiones Mathematicae Graph Theory

Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like partial...

Trees and matchings.

Kenyon, Richard W., Propp, James G., Wilson, David B. (2000)

The Electronic Journal of Combinatorics [electronic only]

Trees with equal 2-domination and 2-independence numbers

Mustapha Chellali, Nacéra Meddah (2012)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization...

Trees with equal restrained domination and total restrained domination numbers

Joanna Raczek (2007)

Discussiones Mathematicae Graph Theory

For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We characterize...

Trees with equal total domination and total restrained domination numbers

Xue-Gang Chen, Wai Chee Shiu, Hong-Yu Chen (2008)

Discussiones Mathematicae Graph Theory

For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained...

Currently displaying 501 – 520 of 561