اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNote on group irregularity strength of disconnected graphs
62
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 o
f 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)$.
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 labe
ls 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.
A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to ${1,2,ldots,m}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u in V(D)$ for a labelin
g is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An antimagic orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz, M$ddot{u}$tze and Schwartz in [J. Graph Theory 64(2010)219-232] raised the question: Does every graph admits an antimagic orientation? It had been proved that for any integer $d$, every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider the 2$d$-regular graph with many odd components. We show that every 2$d$-regular graph with any odd components has an antimagic orientation provide each odd component with enough order.
A semi-proper orientation of a given graph $G$, denoted by $(D,w)$, is an orientation $D$ with a weight function $w: A(D)rightarrow mathbb{Z}_+$, such that the in-weight of any adjacent vertices are distinct, where the in-weight of $v$ in $D$, denote
d by $w^-_D(v)$, is the sum of the weights of arcs towards $v$. The semi-proper orientation number of a graph $G$, denoted by $overrightarrow{chi}_s(G)$, is the minimum of maximum in-weight of $v$ in $D$ over all semi-proper orientation $(D,w)$ of $G$. This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of $G$. The optimal semi-proper orientation is a semi-proper orientation $(D,w)$ such that $max_{vin V(G)}w_D^-(v)=overrightarrow{chi}_s(G)$. Araujo et al. (2016) showed that $overrightarrow{chi}(G)le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$, $overrightarrow{chi}_s(G) le 3$ and the bound is tight. Ara{u}jo et al. (2015) asked whether there is a constant $c$ such that $overrightarrow{chi}(G)le c$ for all outerplanar graphs $G.$ While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph $G,$ $overrightarrow{chi}_s(G)le 4$ and the bound is tight.
A near-factor of a finite simple graph $G$ is a matching that saturates all vertices except one. A graph $G$ is said to be near-factor-critical if the deletion of any vertex from $G$ results in a subgraph that has a near-factor. We prove that a conne
cted graph $G$ is near-factor-critical if and only if it has a perfect matching. We also characterize disconnected near-factor-critical graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
