251. Edgeconnectivity of strong products of graphsBoštjan Brešar, Simon Špacapan, 2007, izvirni znanstveni članek Opis: The strong product ▫$G_1 \boxtimes G_2$▫ of graphs ▫$G_1$▫ and ▫$G_2$▫ is the graph with ▫$V(G_1) \times V(G_2)$▫ as the vertex set, and two distinct vertices ▫$(x_1,x_2)$▫ and ▫$(y_1,y_2)$▫ are adjacent whenever for each ▫$i\in \{1,2\}$▫ either ▫$x_i=y_i$▫ or ▫$x_iy_i \in E(G_i)$▫. In this note we show that for two connected graphs ▫$G_1$▫ and ▫$G_2$▫ the edgeconnectivity ▫$\lambda(G_1 \boxtimes G_2)$▫ equals ▫$\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(V(G_2)+2E(G_2)), \lambda(G_2)(V(G_1)+2E(G_1))\}$▫. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs. Ključne besede: mathematics, graph theory, connectivity, strong product, graph product, separating set Objavljeno: 31.03.2017; Ogledov: 381; Prenosov: 153 Celotno besedilo (173,26 KB) Gradivo ima več datotek! Več...

252. Isomorphic components of Kronecker product of bipartite graphsPranava Jha, Sandi Klavžar, Blaž Zmazek, 1997, izvirni znanstveni članek Opis: Weichsel (Proc. Amer. Math. Soc. 13 (1992), 4752) 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. Ključne besede: mathematics, graph theory, Kronecker graph product, bipartite graphs, graph isomorphism Objavljeno: 31.03.2017; Ogledov: 282; Prenosov: 174 Celotno besedilo (109,31 KB) Gradivo ima več datotek! Več...

253. Median and quasimedian direct products of graphsBoštjan Brešar, Pranava Jha, Sandi Klavžar, Blaž Zmazek, 2005, izvirni znanstveni članek Opis: 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 \times P_3$▫ 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 \times K_2$▫ are proved, and it is shown that the only nonbipartite quasimedian direct product is ▫$K_3 \times K_3$▫. Ključne besede: mathematics, graph theory, median graph, direct product, quasimedian graph, isometric embeddings, convexity Objavljeno: 31.03.2017; Ogledov: 288; Prenosov: 136 Celotno besedilo (174,14 KB) Gradivo ima več datotek! Več...

254. nary transit functions in graphsManoj Changat, Joseph Mathews, Iztok Peterin, Prasanth G. NarasimhaShenoi, 2010, izvirni znanstveni članek Opis: ▫$n$▫ary transit functions are introduced as a generalization of binary (2ary) transit functions. We show that they can be associated with convexities in natural way and discuss the Steiner convexity as a natural ▫$n$▫ary generalization of geodesicaly convexity. Furthermore, we generalize the betweenness axioms to ▫$n$▫ary transit functions and discuss the connectivity conditions for underlying hypergraph. Also ▫$n$▫ary all paths transit function is considered. Ključne besede: mathematics, graph theory, narity, transit function, betweenness, Steiner convexity Objavljeno: 31.03.2017; Ogledov: 346; Prenosov: 145 Celotno besedilo (143,68 KB) Gradivo ima več datotek! Več...

255. On [Theta]graphs of partial cubesSandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek Opis: The ▫$\Theta$▫graph ▫$\Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the DjokovicWinkler relation. ▫$\Theta$▫graphs that are 2connected, trees, or complete graphs are characterized. In particular, ▫$\Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$\Theta$▫graphs are also compared with familiar concepts of crossing graphs and ▫$\tau$▫graphs. Ključne besede: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs Objavljeno: 31.03.2017; Ogledov: 287; Prenosov: 33 Celotno besedilo (150,56 KB) Gradivo ima več datotek! Več...

256. On acyclic colorings of direct productsSimon Špacapan, Aleksandra Tepeh, 2008, izvirni znanstveni članek Opis: A coloring of a graph ▫$G$▫ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees ▫$T_1$▫ and ▫$T_2$▫ equals ▫$\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$▫. We also prove that the acyclic chromatic number of direct product of two complete graphs ▫$K_m$▫ and ▫$K_n$▫ is ▫$mnm2$▫, where ▫$m \ge n \ge 4$▫. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised. Ključne besede: mathematics, graph theory, coloring, acyclic coloring, distancetwo coloring, direct product Objavljeno: 31.03.2017; Ogledov: 207; Prenosov: 38 Celotno besedilo (142,13 KB) Gradivo ima več datotek! Več...

257. 
258. On Vizing's conjectureBoštjan Brešar, 2001, izvirni znanstveni članek Opis: A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫. Ključne besede: mathematics, graph theory, graph, Cartesian product, domination number Objavljeno: 31.03.2017; Ogledov: 433; Prenosov: 47 Celotno besedilo (126,98 KB) Gradivo ima več datotek! Več...

259. Recognizing weighted directed Cartesian graph bundlesBlaž Zmazek, Janez Žerovnik, 2000, izvirni znanstveni članek Opis: In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used.The first one is the new relation ▫$\vec{\delta}^\ast$▫ defined among the arcs of a digraph as a weighted directed analogue of the wellknown relation ▫$\delta^\ast$▫. The second one is the concept of halfconvex subgraphs. A subgraph ▫$H$▫ is halfconvex in ▫$G$▫ if any vertex ▫$x \in G \setminus H$▫ has at most one predecessor and at most one successor Ključne besede: mathematics, graph theory, graph bundles, Cartesian graph product, weighted digraphs, halfconvexity Objavljeno: 31.03.2017; Ogledov: 334; Prenosov: 166 Celotno besedilo (240,86 KB) Gradivo ima več datotek! Več...

260. Some results on total domination in direct products of graphsPaul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Špacapan, izvirni znanstveni članek Opis: Upper and lower bounds on the total domination number of the direct product ofgraphs are given. The bounds involve the ▫$\{2\}$▫total domination number, the total 2tuple 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. Ključne besede: mathematics, graph theory, direktni produkt, total domination, ▫$k$▫tuple domination, open packing, domination Objavljeno: 31.03.2017; Ogledov: 357; Prenosov: 176 Celotno besedilo (156,67 KB) Gradivo ima več datotek! Več...
