In this paper the Cartesian product topology for an arbitrary family of topological spaces and some of its basic properties are defined. The space is investigated to determine which of the separation properties of the component spaces are invariant.

Let $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ denote the Cartesian product of the graphs $G$ and $H$. Domination of the Cartesian product of two graphs has received much attention, with a main objective to confirm the truth of Vizing's well-known conjecture. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the respective domination numbers. The potential truth of Vizing's conjecture gives rise to investigating the domination of graph products that generalizes the Cartesian product. The generalized prism $\pi G$ of $G$ is the graph consisting of two copies of $G$, with edges between the copies determined by a permutation $\pi$ acting on the vertices of $G$. A generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is defined here, incorporating structural properties of both the Cartesian product of two graphs as well as the generalized prism of a graph. Conditions on the isomorphism of two generalized Cartesian products are explored first, establishing a characterization in the case of natural isomorphisms. A comparison of the diameter of the generalized Cartesian product and the corresponding Cartesian product graph is used to illustrate the structural differences between these graph products. This comparison is continued through a study of the validity of an inequality similar to Vizing's conjecture for Cartesian products. Graphs that attain equality in the general bounds for the domination number of the Cartesian product and generalized Cartesian product are investigated in more detail. For any graph $G$ and $n\geq 2$, $\min\{|V(G)|,\gamma(G)+n-2\}\leq\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})\leq n\gamma(G)$. A graph $G$ is called a consistent Cartesian fixer if $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})=\gamma(G)+n-2$ for each $n$ such that $2\leq n<|V(G)|-\gamma(G)+2$. A graph attaining equality in the stated upper bound on $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})$ is called a Cartesian $n$-multiplier. Both of these classes are characterized. Concerning the generalized Cartesian product, $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} K_{n})\leq n\gamma(G)$ for any graph $G$, permutation $\pi$ and $n\geq 2$. A graph attaining equality in the upper bound for all $\pi$ is called a universal multiplier. Such graphs are characterized similar to a known result for generalized prisms. A similar problem for the product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} C_{n}$ is considered, with conditions on a graph being a so-called cycle multiplier provided. A graph attaining equality in the lower bound $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H)\geq\gamma(G)$ for some permutation $\pi$ is called a $\pi$-$H$-fixer. A brief investigation is conducted into the existence of universal $H$-fixers, i.e.~graphs that are $\pi$-$H$-fixers for some $H$ and all permuations $\pi$ of $V(G)$, and it is shown that no such graphs exist when $n\geq 3$. A known efficient algorithm for determining $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} P_{n})$ is surveyed, and modified to accommodate any Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$, thereby establishing a general framework for evaluating the domination number of $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ for a fixed graph $G$ and any $H$. An algorithm to determine $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} T)$ for any tree $T$ is provided, and it is observed to be polynomial for trees of bounded maximum degree. The general framework for $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ is also modified to accommodate the generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$. The study diverts from the main topic of domination to investigate the planarity of the generalized Cartesian product graph. If both $G$ and $H$ are 2-connected graphs, then $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is nonplanar. A known simple polynomial-time planarity testing algorithm is surveyed, and used to establish conditions on the planarity of $P_{m}\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} P_{n}$, the generalized Cartesian product of two paths. This research aims to lay the foundation on which further properties of the generalized Cartesian product and further generalizations may be studied, as well as to provide various open problems to spark interest in the research area.

The complementary prism of a graph G is the graph formed from a disjoint union of G and its complement ̄G by adding the edges of a perfect matching between the corresponding vertices of G and G. We study independent domination numbers of complementary prisms. Exact values are determined for complementary prisms of paths, complete bipartite graphs, and subdivided stars. A natural lower bound on the independent domination number of a complementary prism is given, and graphs attaining this bound axe characterized. Then we show that the independent domination number behaves somewhat differently in complementary prisms than the domination and total domination numbers. We conclude with a sharp upper bound.

The complementary prism of a graph G is the graph formed from a disjoint union of G and its complement ̄G by adding the edges of a perfect matching between the corresponding vertices of G and G. We study independent domination numbers of complementary prisms. Exact values are determined for complementary prisms of paths, complete bipartite graphs, and subdivided stars. A natural lower bound on the independent domination number of a complementary prism is given, and graphs attaining this bound axe characterized. Then we show that the independent domination number behaves somewhat differently in complementary prisms than the domination and total domination numbers. We conclude with a sharp upper bound.

Let G be a graph and Ḡ be the complement of G. The complementary prism GḠ of G is the graph formed from the disjoint union of G and Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. For example, if G is a 5-cycle, then GḠ is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, max {γ(G), γ(Ḡ)} ≤ γ (Ḡ)and max {γt(G), γt(Ḡ)} ≤ γt (Gγ), where γ(G) and γt(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S. A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

The complementary prism GG of a graph G is formed from the disjoint union of G and its complement G by adding the edges of a perfect match- ing between the corresponding vertices of G and G. A Roman dominating function on a graph G = (V,E) is a labeling f : V(G) → {0,1,2} such that every vertex with label 0 is adjacent to a vertex with label 2. The Roman domination number γR(G) of G is the minimum f(V ) = Σv∈V f(v) over all such functions of G. We study the Roman domination number of complementary prisms. Our main results show that γR(GG) takes on a limited number of values in terms of the domination number of GG and the Roman domination numbers of G and G.

No description available.

Title: Reasoning in Description Logics Author: Mgr. Jaromír Malenko Department: Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague Supervisor: Prof. RNDr. Petr Štěpánek, DrSc.; Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague Keywords: Description logic, Reasoner, Cartesian product, Non-monotonic reasoning Abstract: We deal with several aspects of reasoning in Description Logics. First, since description logic (DL) is a subset of First Order Logic (FOL), we use a FOL reasoner to reason in DL. We implemented dl2fol, a DL reasoner that takes an ontology (a DL theory with rules), translates it into a FOL theory, passes this set of formulae to an underling FOL reasoner, and interprets the result in terms of given ontology. This is an effective method for reasoning with newly introduced language constructors. However, we observed longer running times and that satisfiability of some DL concepts wasn't proved due to FOL undecidability. Second, we extend two DLs by introducing new language construct: cartesian product (CP) of concepts and roles. This allows for expressing relationships, that are not expressible by other means in weaker DLs. We...

Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs.