Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: block graph

Sortuj według:

Ogranicz wyniki do:

On three domination-based identification problems in block graphs

100%

Chakraborty D. , Foucaud F. , Parreau A. , Wagler A.

tom Vol. 191, nr 3-4

197--229

The problems of determining the minimum-sized identifying, locating-dominating and open locating-dominating codes of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set C of a graph G such that the vertices of a chosen subset of V (G) (i.e. either V (G) \ C or V (G) itself) are uniquely determined by their neighborhoods in C. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or blocks) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature — with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight

On the General Position Number of Complementary Prisms

88%

Neethu P. K. , Chandran S. V. U. , Changat M. , Klavžar S.

tom Vol. 178, nr 3

267--281

The general position number gp(G ) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n (G ) + 1 if G is connected and gp(G G ¯ ) ≤ n (G ) if G is disconnected. Graphs G for which gp(G G ¯ ) = n (G ) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n (G ), n (G )+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n (G ) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.