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 4 Next

Displaying 61 – 80 of 561

Showing per page

The classification of finite groups by using iteration digraphs

Uzma Ahmad, Muqadas Moeen (2016)

Czechoslovak Mathematical Journal

A digraph is associated with a finite group by utilizing the power map f : G → G defined by f ( x ) = x k for all x ∈ G , where k is a fixed natural number. It is denoted by γ G ( n , k ) . In this paper, the generalized quaternion and 2 -groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a 2 -group are determined for a 2 -group to be a generalized quaternion group. Further, the classification of two generated 2 -groups as abelian or non-abelian...

The cobondage number of a graph

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

Discussiones Mathematicae Graph Theory

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 type...

The color-balanced spanning tree problem

Štefan Berežný, Vladimír Lacko (2005)

Kybernetika

Suppose a graph G = ( V , E ) whose edges are partitioned into p disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number p of categories and present some polynomial algorithm.

The complexity of short schedules for uet bipartite graphs

Evripidis Bampis (2010)

RAIRO - Operations Research

We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F. C. Walters (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters, 
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput. 37 (2007) 977–1013].

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F.C. Walters (2011)

RAIRO - Theoretical Informatics and Applications

We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters, 
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput.37 (2007) 977–1013].

The connected forcing connected vertex detour number of a graph

A.P. Santhakumaran, P. Titus (2011)

Discussiones Mathematicae Graph Theory

For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset...

The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

Michitaka Furuya (2014)

Discussiones Mathematicae Graph Theory

An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine...

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor...

Currently displaying 61 – 80 of 561