On the fixing sets of dihedral groups

The fixing number of a graph $\Gamma$ is the minimum number of labeled vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of $\Gamma$. The fixing set of a finite group $G$ is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to $G$. Previously, authors have studied the fixing sets of both abelian groups and symmetric groups. In this article, we determine the fixing set of the dihedral group.     

Destroying automorphisms by fixing nodes

The fixing number of a graph G is the minimum cardinality of a set S⊂V(G) such that every nonidentity automorphism of G moves at least one member of S, i.e., the automorphism group of the graph obtained from G by fixing every node in S is trivial. We provide a formula for the fixing number of a disconnected graph in terms of the fixing numbers of its components and make some observations about graphs with small fixing numbers. We determine the fixing number of a tree and find a necessary and sufficient condition for a tree to have fixing number 1.     

On the classification of linear complementary dual codes

We give a complete classification of binary linear complementary dual codes of lengths up to 13 and ternary linear complementary dual codes of lengths up to 10.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

Sharply k-arc-transitive-digraphs: Finite and infinite examples

A general method for constructing sharply $k$-arc-transitive digraphs, i.e. digraphs that are $k$-arc-transitive but not $(k+1)$-arc-transitive, is presented. Using our method it is possible to construct both finite and infinite examples. The infinite examples can have one, two or infinitely many ends. Among the one-ended examples there are also digraphs that have polynomial growth.     

Graphs with at most one crossing

The crossing number of a graph $G$ is the least number of crossings over all possible drawings of $G$. We present a structural characterization of graphs with crossing number one.     

Large orbit sizes in finite group actions

In this paper, we study the relations of the sizes of various sections of finite linear groups and the largest orbit size of the linear group actions. We also study various applications of those orbit theorems.     

二秩无扭群的自同构群和只有两个自同构的二秩无扭群

本文利用Ｋｕｒǒｓ不变量理论和不定方程理论，讨论了二秩无扭群的自同构群，以及有零高元的二秩无扭群只有两个自同构的充要条件．     

Separation theorems for nonconvex sets and application in optimization

The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.     

On the smallest non-trivial tight sets in Hermitian polar spaces H(d,q2), d even

We show that every $x$-tight set of a Hermitian polar spaces $\mathrm{H}(2n,q^2)$, $n\ge 2$, is the union of $x$ disjoint generators of the polar space provided that $x\le \frac{1}{2}(q+1)$. This was known before only when $n\in \{2,3\}$. This result is a contribution to the conjecture that the smallest $x$-tight set of $H(2n,q^2)$ that is not a union of disjoint generators occurs for $x=q+1$ and is for sufficiently large $q$ an embedded subgeometry.     

A lower bound on the size of an absorbing set in an arc-coloured tournament

Bousquet, Lochet and Thomassé recently gave an elegant proof that for any integer $n$, there is a least integer $f\left(n\right)$ such that any tournament whose arcs are coloured with $n$ colours contains a subset of vertices $S$ of size $f\left(n\right)$ with the property that any vertex not in $S$ admits a monochromatic path to some vertex of $S$. In this note we provide a lower bound on the value $f\left(n\right)$.     

Partial category actions on sets and topological spaces

We introduce (continuous) partial category actions on sets (topological spaces) and show that each such action admits a universal globalization. Thereby, we obtain a simultaneous generalization of corresponding results for groups, by Abadie, and Kellendonk and Lawson, and for monoids, by Megrelishvili and Schröder. We apply this result to the special case of partial groupoid actions where we obtain a sharpening of a result by Gilbert, concerning ordered groupoids, in the sense that mediating functions between universal globalizations always are injective.     

H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups

We consider the structure of $H$-free subgraphs of graphs with high minimal degree. We prove that for every $k>m$ there exists an $???(k,m)>0$ so that the following holds. For every graph $H$ with chromatic number $k$ from which one can delete an edge and reduce the chromatic number, and for every graph $G$ on $n>n_0\left(H\right)$ vertices in which all degrees are at least $(1??)n$, any subgraph of $G$ which is $H$-free and contains the maximum number of copies of the complete graph $K_m$ is $(k?1)$-colorable.We also consider several extensions for the case of a general forbidden graph $H$ of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Average eccentricity,k-packing and k-domination in graphs

Let $G$ be a connected graph. The eccentricity $e\left(v\right)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$. The average eccentricity $\mathrm{avec}\left(G\right)$ of $G$ is defined as the average of the eccentricities of the vertices of $G$, i.e., as $\frac{1}{\left|V\right|}{\sum }_{v\in V}e\left(v\right)$, where $V$ is the vertex set of $G$. For $k\in \mathbb{N}$, the $k$-packing number of $G$ is the largest cardinality of a set of vertices of $G$ whose pairwise distance is greater than $k$. A $k$-dominating set of $G$ is a set $S$ of vertices such that every vertex of $G$ is within distance $k$ from some vertex of $S$. The $k$-domination number (connected $k$-domination number) of $G$ is the minimum cardinality of a $k$-dominating set (of a $k$-dominating set that induces a connected subgraph) of $G$. For $k=1$, the $k$-packing number, the $k$-domination number and the connected $k$-domination number are the independence number, the domination number and the connected domination number, respectively. In this paper we present upper bounds on the average eccentricity of graphs in terms of order and either $k$-packing number, $k$-domination number or connected $k$-domination number.