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

Displaying 101 – 120 of 8548

Showing per page

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is w ( f ) = ∑ v ∈ V f ( v ) . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called...

A characterization of the interval function of a (finite or infinite) connected graph

Ladislav Nebeský (2001)

Czechoslovak Mathematical Journal

By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval...

A characterization of the set of all shortest paths in a connected graph

Ladislav Nebeský (1994)

Mathematica Bohemica

Let G be a (finite undirected) connected graph (with no loop or multiple edge). The set ℒ of all shortest paths in G is defined as the set of all paths ξ , then the lenght of ξ does not exceed the length of ς . While the definition of ℒ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of ℒ : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...

A Characterization of Trees for a New Lower Bound on the K-Independence Number

Nacéra Meddah, Mostafa Blidia (2013)

Discussiones Mathematicae Graph Theory

Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. The maximum cardinality of a k-independent set of G is the k-independence number βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv are the chromatic number, the number of supports vertices and the number of leaves neighbors of v, in the graph G, respectively. Moreover,...

A characterization of (γₜ,γ₂)-trees

You Lu, Xinmin Hou, Jun-Ming Xu, Ning Li (2010)

Discussiones Mathematicae Graph Theory

Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.

A class of latin squares derived from finite abelian groups

Anthony B. Evans (2014)

Commentationes Mathematicae Universitatis Carolinae

We consider two classes of latin squares that are prolongations of Cayley tables of finite abelian groups. We will show that all squares in the first of these classes are confirmed bachelor squares, squares that have no orthogonal mate and contain at least one cell though which no transversal passes, while none of the squares in the second class can be included in any set of three mutually orthogonal latin squares.

A class of tight circulant tournaments

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2000)

Discussiones Mathematicae Graph Theory

A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.

A class of weakly perfect graphs

H. R. Maimani, M. R. Pournaki, S. Yassemi (2010)

Czechoslovak Mathematical Journal

A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.

Currently displaying 101 – 120 of 8548