The Edge Rotation Graph

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n ²). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

More on monochromatic-rainbow Ramsey type theorems

An edge colored graph is called a rainbow if no two of its edges have the same color. Let ? and $\mathcal{G}$ be two families of graphs. Denote by $RM({\mathcal{H}},\mathcal{G})$ the smallest integer R, if it exists, having the property that every coloring of the edges of K _R by an arbitrary number of colors implies that either there is a monochromatic subgraph of K _R that is isomorphic to a graph in ? or there is a rainbow subgraph of K _R that is isomorphic to a graph in $\mathcal{G}$ . ${\mathcal{T}}_{n}$ is the set of all trees on n vertices. ${\mathcal{T}}_{n}(k)$ denotes all trees on n vertices with diam(T _n (k))≤k. In this paper, we investigate $RM({\mathcal{T}}_{n},4K_{2})$ , $RM({\mathcal{T}}_{n},K_{1,4})$ and $RM({\mathcal{T}}_{n}(4),K_{3})$ .     

Suitable families of boxes and kernels of staircase starshaped sets in {\mathbb{R}^d}

Let S be an orthogonal polytope in ${\mathbb{R}^d}$ . There exists a suitable family ${\mathcal{C}}$ of boxes with ${S = \cup \{C : C {\rm in} \mathcal{C}\}}$ such that the following properties hold:

The staircase kernel Ker S is a union of boxes in ${\mathcal{C}}$ . Let ${\mathcal{V}}$ be the family of vertices of boxes in ${\mathcal{C}}$ , and let ${v_o\, \epsilon \mathcal{V}}$ . Point v _o belongs to Ker S if and only if v _o sees via staircase paths in S every point w in ${\mathcal{V}}$ . Moreover, these staircase paths may be selected to consist of edges of boxes in ${\mathcal{C}}$ . Let B be a box in ${\mathcal{C}}$ with vertices of B in Ker S. Box B lies in Ker S if and only if, for some b in rel int B and for every translate H of a coordinate hyperplane at ${b, b \epsilon}$ Ker (H ∩ S). For point p in S, p belongs to Ker S if and only if, for every x in S, there exist some p ? x geodesic λ (p, x) and some corresponding ${\mathcal{C}}$ - chain D containing λ (p, x) such that D is staircase starshaped at p.

     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of  \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

Left Orders in Special Completely 0-Simple Semigroups

A subsemigroup S of a semigroup Q is a left order in Q, and Q is a semigroup of left quotients of S, if every element of Q can be written as a ^?1 b for some ${a, b\in S}$ with a belonging to a group ${\mathcal{H}}$ -class of Q. Characterizations are provided for semigroups which are left orders in completely 0-simple semigroups in the following classes: without similar ${\mathcal{L}}$ -classes, without contractions, ${\mathcal{R}}$ -unipotent, Brandt semigroups and their generalization. Complete discussion of two examples and an idea for a new concept conclude the paper.     

Forbidden Induced Subgraphs for Perfect Matchings

Let ${\mathcal{F}}$ be a family of connected graphs. A graph G is said to be ${\mathcal{F}}$ -free if G is H-free for every graph H in ${\mathcal{F}}$ . We study the problem of characterizing the families of graphs ${\mathcal{F}}$ such that every large enough connected ${\mathcal{F}}$ -free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1–12, 2005), Fujita et al. (J Combin Theory Ser B 96(3):315–324, 2006) and Ota et al. (J Graph Theory, 67(3):250–259, 2011), where the authors were able to characterize such graph families ${\mathcal{F}}$ restricted to the cases ${|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}$ and ${|\mathcal{F}| \leq 3}$ , respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition ${|\mathcal{F}| \leq k}$ for some k ≥ 4.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

Symmetric Graphs from Polytopes of High Rank

Given a polytope ${{\mathcal{P}}}$ of rank 2n, the faces of middle ranks n ? 1 and n constitute the vertices of a bipartite graph, the medial layer graph ${{M(\mathcal{P})}}$ of ${{\mathcal{P}}}$ . The group ${{D(\mathcal{P})}}$ of automorphisms and dualities of ${{\mathcal{P}}}$ has a natural action on this graph. We prove algebraic and combinatorial conditions on ${{\mathcal{P}}}$ that ensure this action is transitive on k-arcs in ${{M(\mathcal{P})}}$ for some small k (in particular focussing on k?=?3), and provide examples of families of polytopes that satisfy these conditions. We also examine how ${{D(\mathcal{P})}}$ acts on the k-stars based at vertices of ${{M(\mathcal{P})},}$ and describe self-dual regular polytopes (in particular those of rank 6) for which this action is transitive on the k-stars for small k.     

Some relations on the ordering of trees by minimal energies between subclasses of trees

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. A tree is said to be non-starlike if it has at least two vertices with degree more than 2. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let $\mathcal{T}_{n,d}$ , $\mathbb{T}_{n,p}$ be the set of all trees of order n with diameter d, p pendent vertices respectively. In this paper, we investigate the relations on the ordering of trees and non-starlike trees by minimal energies between $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ . We first show that the first two trees (non-starlike trees, resp.) with minimal energies in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same for 3≤d≤n?2 (3≤d≤n?3, resp.). Then we obtain that the trees with third-minimal energy in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same when n≥11, 3≤d≤n?2 and d≠8; and the tree with third-minimal energy in $\mathcal{T}_{n,8}$ is the caterpillar with third-minimal energy in $\mathbb{T}_{n,n-7}$ for n≥11.     

Bounded Degree, Triangle Avoidance Graph Games

We consider variants of the triangle-avoidance game first defined by Harary and rediscovered by Hajnal a few years later. A graph game begins with two players and an empty graph on n vertices. The two players take turns choosing edges within K _n , building up a simple graph. The edges must be chosen according to a set of restrictions ${\mathcal{R}}$ . The winner is the last player to choose an edge that does not violate any of the restrictions in ${\mathcal{R}}$ . For fixed n and ${\mathcal{R}}$ , one of the players has a winning strategy. For various games where ${\mathcal{R}}$ includes bounded degree and triangle avoidance, we determine the winner for all values of n.     

Proper/Residually-Finite Idempotent Semirings

An idempotent semiring (= ISR) is called L-E if its underlying additive Abelian semigroup is generated by join-primes. Not all ISRs are L-E; not even when finite. The submodule of “linear-recognizable” elements of an ISR $\mathcal {M}$ is denoted $\mathcal {C}\mathcal {M}$ , and $\mathcal {M}$ is called proper if there are enough elements in $\mathcal {C}\mathcal {M}$ to separate points. If there are enough finite-index congruences to separate points, $\mathcal {M}$ is called residually-finite. Finite and proper ISRs are always residually-finite, but finite ISRs are not always proper, unless they are L-E. For certain classes of ISRs, conditions are given to guarantee proper and residual-finiteness. Among these is one which requires that the compact elements of the linear dual of $\mathcal {M}$ belong to $\mathcal {C}\mathcal {M}$ . Another condition requires that the recognizable subsets of a certain underlying monoid remain recognizable under the closure operator relative to a certain natural topology. These conditions are automatic for any finite L-E ISR, or any L-E ISR arising from a bounded, distributive lattice. Thus, a large class of proper/residually-finite ISRs exists. Moreover, the theorem of Malcev for semigroups (finitely-generated, commutative implies residually-finite) is shown to fail for ISRs in general.     

On the Relaxed Colouring Game and the Unilateral Colouring Game

In the paper we introduce the new game—the unilateral \({\mathcal{P}}\) -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property \({\mathcal {P}}\) and a set C of r colours. In the unilateral \({\mathcal {P}}\) -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral \({\mathcal {P}}\) -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property \({\mathcal {P}}\) . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The \({\mathcal {P}}\) -unilateral game chromatic number, denoted by \({\chi_{ug}^\mathcal {P}(G)}\) , is the least number r for which Alice has a winning strategy for the unilateral \({\mathcal {P}}\) -colouring game with r colours on G. We prove that the \({\mathcal {P}}\) -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral \({\mathcal {P}}\) -colouring game. Moreover, for k ≥  2 we define a class of graphs \({\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}\) . The class \({\mathcal {H}_k }\) contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let \({\mathcal {S}_d}\) be the class of graphs with maximum degree at most d. We find the upper bound for the \({\mathcal {S}_2}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_3}\) and we study the \({\mathcal {S}_d}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_4}\) for \({d \in \{2,3\}}\) . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if \({G \in \mathcal {H}_k}\) , then \({\chi_g^{(d)}(G) \leq k + 2-d}\) , for \({k \in \{3, 4\}}\) and \({d \in \{0, \ldots, k-1\}}\) . This generalizes a known result for trees.     

The cardinality of β A (S J )

Let J be an infinite set and let $I=\mathcal{P}_{f}( J)$ . For i??I, define $\mathcal{B}_{J}( i) =\{ f\mid f:\mathcal{P}( i) \rightarrow \mathcal{P}( i) \} $ and let $$S_{J}=\{ ( i,f) \mid i\in I\text{ and } f\in \mathcal{B}_{J}( i) \}.$$ For (i,f), (k,g)??S _J , define $f\ast g:\mathcal{P}( i\cup k) \rightarrow \mathcal{P}( i\cup k) $ as follows. For $x\in \mathcal{P}( i\cup k) $ , let $$( f\ast g) ( x) =\left\{\begin{array}{l@{\quad }l}g( x) , & \text{if\ }x=\emptyset, \\g( x\cap k) , & \text{if\ }x\cap k\neq \emptyset, \\f( x) , & \text{if\ }x\in \mathcal{P}( i\backslash k)\text{ and }x\neq \emptyset.\end{array}\right.$$ Define (i,f)?(k,g)=(i??k,f?g). It is shown that (S _J ,?) is a semigroup. Let ??S _J denote the collection of all ultrafilters on the set S _J . We consider (??S _J ,?), the compact (Hausdorff) right topological semigroup that is the Stone?C?ech Compactification of the semigroup (S _J ,?) equipped with the discrete topology. Similar to the construction in Grainger (Semigroup Forum 73:234?C242, 2006), it is shown that there is an injective map A???? _A (S _J ) of $\mathcal{P}( J) $ into $\mathcal{P}( \beta S_{J}) $ such that each ?? _A (S _J ) is a closed subsemigroup of (??S _J ,?), the set ?? _J (S _J ) is the smallest ideal of (??S _J ,?) and the collection $\{ \beta_{A}( S_{J}) \mid A\in \mathcal{P}( J) \} $ is a partition of???S _J . The main result is establishing that the cardinality of??? _A (S _J ) is $2^{2^{\vert J\vert }}$ for any?A?J.     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

Module amenability of the second dual and module topological center of semigroup algebras

In this paper we define the module topological center of the second dual $\mathcal{A}^{**}$ of a Banach algebra $\mathcal{A}$ which is a Banach $\mathfrak{A}$ -module with compatible actions on another Banach algebra $\mathfrak{A}$ . We calculate the module topological center of ? ¹(S)^**, as an ? ¹(E)-module, for an inverse semigroup S with an upward directed set of idempotents E. We also prove that ? ¹(S)^** is ? ¹(E)-module amenable if and only if an appropriate group homomorphic image of S is finite.     

Almost periodic events generated by random flows

Under suitable conditions, a measurable action of a semigroup S on a probability space $(\varOmega,\mathcal {F},\mu )$ generates various σ-fields reflecting the dynamical properties of the associated representation of S and containing the information provided by certain subspaces of $\mathcal {L}^{1}(\mu )$ determined by the representation. For example, the functions in $\mathcal {L}^{1}(\mu )$ with norm relatively compact orbits under S are precisely the $\mathcal {L}^{1}$ functions that are measurable with respect to the σ-field of almost periodic events. In the special case of a measure-preserving action, the minimal projection operator associated with the action is a conditional expectation with respect to this σ-field, leading to a result on transformation of martingales. The unifying construct throughout the paper is the weakly almost periodic compactification of S, a powerful tool that provides a convenient platform to study operator semigroups associated with the action.     

A note on maximal regular subsemigroups of the finite transformation semigroups \mathcal{T}(n,r)

Let $\mathcal{T}_{n}$ be the semigroup of all full transformations on the finite set X _n ={1,2,…,n}. For 1≤r≤n, set $\mathcal {T}(n, r)=\{ \alpha\in\mathcal{T}_{n} | \operatorname{rank}(\alpha)\leq r\}$ . In this note we show that, for 2≤r≤n?2, any maximal regular subsemigroup of the semigroup $\mathcal{T} (n,r)$ is idempotent generated, but this may not happen in the semigroup $\mathcal{T}(n, n-1)$ .     

On the Intersection of the Normalizers of the \boldsymbol{\cal{F}}-Residuals of Subgroups of a Finite Group

In this paper we give criteria for a finite group to belong to a formation. As applications, recent theorems of Li, Shen, Shi and Qian are generalized. Let G  be a finite group, $\cal F$ a formation and p  a prime. Let $D_{\mathcal {F}}(G)$ be the intersection of the normalizers of the $\cal F$ -residuals of all subgroups of G, and let $D_{\mathcal {F}}^{p}(G)$ be the intersection of the normalizers of $(H^{\cal F}O_{p'}(G))$ for all subgroups H of G. We then define $D_{\mathcal F}^{0}(G)=D_{\mathcal F, p}^{~0}(G)=1$ and $D_{\mathcal F}^{i+1}(G)/D_{\mathcal F}^{i}(G)=D_{\mathcal F}(G/D_{\mathcal F}^{i}(G))$ , $D_{\mathcal F, p}^{i+1}(G)/D_{\mathcal F, p}^{~i}(G)=D_{\mathcal F, p}(G/D_{\mathcal F, p}^{~i}(G))$ . Let $D_{\mathcal {F}}^{\infty}(G)$ and $D_{\mathcal {F}, p}^{~\infty}(G)$ denote the terminal member of the ascending series of $D_{\mathcal F}^{i}(G)$ and $D_{\mathcal F, p}^{~i}(G)$ respectively. In this paper we prove that under certain hypotheses, the the $\cal F$ -residual $G^{\cal F}$ is nilpotent (respectively,p-nilpotent) if and only if $G=D_{\mathcal {F}}^{\infty}(G)$ (respectively, $G=D_{\mathcal {F}, p}^{~\infty}(G)$ ). Further more, if the formation $\cal F$ is either the class of all nilpotent groups or the class of all abelian groups, then $G^{\cal F}$ is p-nilpotent if and only if and only if every cyclic subgroup of G order p and 4 (if p?=?2) is contained in $D_{\mathcal {F}, p}^{~\infty}(G)$ .