No Arabic abstract
We investigate the textit{group irregularity strength}, $s_g(G)$, of a graph, i.e. the least integer $k$ such that taking any Abelian group $mathcal{G}$ of order $k$, there exists a function $f:E(G)rightarrow mathcal{G}$ so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on $s_g(G)$ for a general graph $G$ was exponential in $n-c$, where $n$ is the order of $G$ and $c$ denotes the number of its components. In this note we prove that $s_g(G)$ is linear in $n$, namely not greater than $2n$. In fact, we prove a stronger result, as we additionally forbid the identity element of a group to be an edge label or the sum of labels around a vertex. We consider also locally irregular labelings where we require only sums of adjacent vertices to be distinct. For the corresponding graph invariant we prove the general upper bound: $Delta(G)+{rm col}(G)-1$ (where ${rm col}(G)$ is the coloring number of $G$) in the case when we do not use the identity element as an edge label, and a slightly worse one if we additionally forbid it as the sum of labels around a vertex. In the both cases we also provide a sharp upper bound for trees and a constant upper bound for the family of planar graphs.
We investigate the textit{group irregularity strength} ($s_g(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $gr$ of order $s$, there exists a function $f:E(G)rightarrow gr$ such that the sums of edge labels at every vertex are distinct. So far it was not known if $s_g(G)$ is bounded for disconnected graphs. In the paper we we present some upper bound for all graphs. Moreover we give the exact values and bounds on $s_g(G)$ for disconnected graphs without a star as a component.
We investigate the textit{edge group irregularity strength} ($es_g(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $mathcal{G}$ of order $s$, there exists a function $f:V(G)rightarrow mathcal{G}$ such that the sums of vertex labels at every edge are distinct. In this note we provide some upper bounds on $es_g(G)$ as well as for edge irregularity strength $es(G)$ and harmonious order $rm{har}(G)$.
A graph $G$ is said to be $preceq$-ubiquitous, where $preceq$ is the minor relation between graphs, if whenever $Gamma$ is a graph with $nG preceq Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G preceq Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$. A well-known conjecture of Andreae is that every locally finite connected graph is $preceq$-ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph~$G$ which implies that $G$ is $preceq$-ubiquitous. In particular this implies that the full grid is $preceq$-ubiquitous.
In this paper we compare the brushing number of a graph with the zero-forcing number of its line graph. We prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Using a similar construction, we also prove the conjecture that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph; moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.