Search

A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν ( H ) of H is the size of a maximum matching in H . A subset D of vertices of H is a dominating set of H if for every v ∈ V ∖ D there exists u ∈ D such that u and v lie in an hyperedge of H . The cardinality of a minimum dominating set of H is the domination number of H , denoted by γ ( H ) . It was proved that γ ( H ) ≤ ( r − 1 ) ν ( H ) for r -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ ( H ) = ν ( H ) have been characterized. In this paper we generalize the inequality γ ( H ) ≤ ( r − 1 ) ν ( H ) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ ( H ) = ( r − 1 ) ν ( H ) . [ABSTRACT FROM AUTHOR]

This paper generalizes the tree concept in Graph Theory, which plays a crucial role in many areas of science and technology. This paper also characterizes partial trees using the concept of maximum spanning trees. [ABSTRACT FROM AUTHOR]

The domination number of a graph G is the smallest number of vertices which dominate all remaining vertices by edges of G. The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than the domination number of G. The concept of the bondage number was formally introduced by Fink et al. in 1990. Since then, this topic has received considerable research attention and made some progress, variations, and generalizations. This paper gives a survey on the bondage number, including known results, conjectures, problems, and some comments, also selectively summarizes other types of bondage numbers. [ABSTRACT FROM AUTHOR]

Huang and Liu [Generalized scrambling indices of primitive a digraph, Linear Algebra Appl. 433 (2010), pp. 1798–1808] gave the definitions of the generalized μ-scrambling indices and the generalized scrambling indices of a primitive digraph and also provided some exact lower and upper bounds for the generalized scrambling indices of various classes of primitive digraphs. In this paper, we give some exact lower and upper bounds for the generalized μ-scrambling indices of various classes of primitive digraphs. [ABSTRACT FROM PUBLISHER]

Abstract: The competition graph of a doubly partial order is an interval graph. The competition-common enemy graph, a variant of the competition graph, of a doubly partial order is also an interval graph if it does not contain a 4-cycle as an induced subgraph. It is natural to ask whether or not the same phenomenon occurs for other interesting variants of the competition graph. In this paper, we study the -step competition graph, a generalization of the competition graph, of a doubly partial order. We show that the -step competition graph of a doubly partial order is an interval graph for every positive integer . We also show that given a positive integer , an interval graph with sufficiently many isolated vertices is the -step competition graph of a doubly partial order. [Copyright &y& Elsevier]