Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On θ-graphs of partial cubes

100%
Klavžar S., Kovse M.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
313-321
EN
The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the rainbow connection of Cartesian products and their subgraphs

100%
Klavžar S., Mekiš G.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
783-793
EN
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Tree-like isometric subgraphs of hypercubes

81%
Brešar B., Imrich W., Klavžar S.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
227-240
EN
Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Isomorphic components of Kronecker product of bipartite graphs

81%
Jha P., Klavžar S., Zmazek B.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
301-309
EN
Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.
5
Content available remote

Domination Game Critical Graphs

81%
Bujtás C., Klavžar S., Košmrlj G.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
781-796
EN
The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game domination number. Here we study the γg-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γg-critical graphs with γg = 2 and with γg = 3, moreover for each n we identify the (infinite) class of all γg-critical ones among the nth powers CnN of cycles. Along the way we determine γg(CnN) for all n and N. Results of a computer search for γg-critical trees are presented and several problems and research directions are also listed.
6
Content available remote

Edge-Transitive Lexicographic and Cartesian Products

81%
Imrich W., Iranmanesh A., Klavžar S., Soltani A.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
857-865
EN
In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
7
Content available remote

How Long Can One Bluff in the Domination Game?

81%
Brešar B., Dorbec P., Klavžar S., Košmrlj G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
337-352
EN
The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs K(n, 2), n ≥ 6, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
8
Content available remote

Sierpiński graphs as spanning subgraphs of Hanoi graphs

81%
Hinz A., Klavžar S., Zemljič S.
Open Mathematics
|
2013
|
tom 11
|
nr 6
1153-1157
EN
Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some results on total domination in direct products of graphs

81%
Dorbec P., Gravier S., Klavžar S., Spacapan S.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
103-112
EN
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Median and quasi-median direct products of graphs

81%
Brešar B., Jha P., Klavžar S., Zmazek B.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
183-196
EN
Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.
11
Content available remote

Strong edge geodetic problem in networks

71%
Manuel P., Klavžar S., Xavier A., Arokiaraj A., Thomas E.
Open Mathematics
|
2017
|
tom 15
|
nr 1
1225-1235
EN
Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. [Math. Comput. Modelling, 1993, 17, 89-95]. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.