Displaying 121 – 140 of 724

Showing per page

A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae (2012)

Serdica Journal of Computing

ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

For a connected graph G = ( V , E ) and a set S V ( G ) with at least two vertices, an S -Steiner tree is a subgraph T = ( V ' , E ' ) of G that is a tree with S V ' . If the degree of each vertex of S in T is equal to 1, then T is called a pendant S -Steiner tree. Two S -Steiner trees are internally disjoint if they share no vertices other than S and have no edges in common. For S V ( G ) and | S | 2 , the pendant tree-connectivity τ G ( S ) is the maximum number of internally disjoint pendant S -Steiner trees in G , and for k 2 , the k -pendant tree-connectivity τ k ( G ) ...

A lower bound for the irredundance number of trees

Michael Poschen, Lutz Volkmann (2006)

Discussiones Mathematicae Graph Theory

Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result. ...

A lower bound for the packing chromatic number of the Cartesian product of cycles

Yolandé Jacobs, Elizabeth Jonck, Ernst Joubert (2013)

Open Mathematics

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...

A magical approach to some labeling conjectures

Ramon M. Figueroa-Centeno, Rikio Ichishima, Francesc A. Muntaner-Batle, Akito Oshima (2011)

Discussiones Mathematicae Graph Theory

In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the...

Currently displaying 121 – 140 of 724