Distance Magic Labeling in Complete 4-partite Graphs

Let G be a complete k-partite simple undirected graph with parts of sizes \(p_1\le p_2\cdots \le p_k\). Let \(P_j=\sum _{i=1}^jp_i\) for \(j=1,\ldots ,k\). It is conjectured that G has distance magic labeling if and only if \(\sum _{i=1}^{P_j} (n-i+1)\ge j{{n+1}\atopwithdelims (){2}}/k\) for all \(j=1,\ldots ,k\). The conjecture is proved for \(k=4\), extending earlier results for \(k=2,3\).     

Magic Labeling of Disjoint Union Graphs

Let G be a graph with vertex set V (G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,|E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+|E(G)|)/2·d(v), where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V (G),|{e:e ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.     

关于图的距离标号问题

图G的L（2，1）-标号是一个从顶点V（G）集到非负整数集的函数f（x），使得若d（x，y）：1，则｜f（x）-f（y）｜≥2；若d（x，y）=2，则｜f（x）-f（y）｜≥1。图G的L（2，1）-标号数A（G）是使得G有max{f（v）：v∈V（G）}=k的L（2，1）-标号中的最小数愚。本文将L（2，1）-标号问题推广到更一般的情形即L（d1，d2，d3）-标号问题，并得出了复合图的λd1，d2，d3（G）的上界。     

Note on Group Distance Magic Graphs G[C 4]

A group distance magic labeling or a ${\mathcal{G}}$ -distance magic labeling of a graph G =  (V, E) with ${|V | = n}$ is a bijection f from V to an Abelian group ${\mathcal{G}}$ of order n such that the weight ${w(x) = \sum_{y\in N_G(x)}f(y)}$ of every vertex ${x \in V}$ is equal to the same element ${\mu \in \mathcal{G}}$ , called the magic constant. In this paper we will show that if G is a graph of order n =  2 ^p (2k + 1) for some natural numbers p, k such that ${\deg(v)\equiv c \mod {2^{p+1}}}$ for some constant c for any ${v \in V(G)}$ , then there exists a ${\mathcal{G}}$ -distance magic labeling for any Abelian group ${\mathcal{G}}$ of order 4n for the composition G[C ₄]. Moreover we prove that if ${\mathcal{G}}$ is an arbitrary Abelian group of order 4n such that ${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$ for some Abelian group ${\mathcal{A}}$ of order n, then there exists a ${\mathcal{G}}$ -distance magic labeling for any graph G[C ₄], where G is a graph of order n and n is an arbitrary natural number.     

有向图的距离标号边跨度

将无向图距离标号边跨度的概念引入到有向图.运用图的流（flow）及tension理论,确定了有向树和有向圈的边跨度,以及最长有向路长不超过3的有向二部图边跨度的可达上下界.     

Distance Between Two Vertices of Maximum Matching Graphs

The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings which differ by exactly one edge. In this paper, we obtain a lower bound of distance between two vertices of maximum matching graph, and give a necessary and sufficient condition that the bound can be reached.     

Binary Labeling of Graphs

Let G = (V, E) be a graph. A mapping f: E(G) → {0, l} ^m is called a mod 2 coding of G, if the induced mapping g: V(G) → {0, l} ^m , defined as \(g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}\) , assigns different vectors to the vertices of G. Note that all summations are mod 2. Let m(G) be the smallest number m for which a mod 2 coding of G is possible. Trivially, m(G) ≥ ?Log₂ |V|?. Recently, Aigner and Triesch proved that m(G) ≤ ?Log₂ |V|? + 4. In this paper, we determine m(G). More specifically, we prove that if each component of G has at least three vertices, then $$mG = \left\{ {\begin{array}{*{20}c} {k,} & {if \left| V \right| \ne 2^k - 2} \\ {k + 1,} & {else} \\ \end{array} ,} \right.$$ where k = ?Log₂ |V|?.     

Antimagic Labeling of Cubic Graphs

An antimagic labeling of a graph G is a one‐to‐one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.     

Antimagic Labeling of Regular Graphs

A graph is antimagic if there is a one‐to‐one correspondence such that for any two vertices , . It is known that bipartite regular graphs are antimagic and nonbipartite regular graphs of odd degree at least three are antimagic. Whether all nonbipartite regular graphs of even degree are antimagic remained an open problem. In this article, we solve this problem and prove that all even degree regular graphs are antimagic.     

关于DNA图及其标号图的进一步研究

2007年,Wang等得到了关于不包含环的DNA标号图的一个结果,在此基础上我们推广到一般有向图上,即任何无孤立点的有向图在友关系下恰有—个等价类的充要条件,并得出几个相应的改进结果.本文还给出了一个定理的反例,进而得到定理的修正和完善.由此容易推出Wang等的一个定理的必要条件也是充分的.     

矩阵与有向图的双标号带宽

定义了一般矩阵与有向图的双标号带宽,并给出了一些理论结果.此外还给出了无向图带宽的一个新结果.     

Modularity of Some Distance Graphs

Doklady Mathematics - New bounds on the modularity of distance graphs were obtained and the exact value of modularity was calculated for G(n, 2, 1) graphs.     

若干并图的优美标号

证明了,对任意大于1的自然数m,n,p,非连通图(■ V ■)∪K_(n,p)是优美图;当k≤p,m=kn+3或m=kn+1时,非连通图(P_2 V ■)∪K_(n,p)是优美图;当p≥2,m=3k+1时,非连通图(P_2 V ■)∪K_(3,p)是优美图;对任意正整数n,p,非连通图(P_1 V P_(2n+2))∪_(n,p)是优美图.     

关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．     

Degree Sequence of Tight Distance Graphs

A graph G on n vertices is a tight distance graph if there exists a set $D\subseteq \{1,2,\dots ,n-1\}$ such that $V(G)=\{0,1,\dots ,n-1\}$ and $ij\in E(G)$ if and only if $|i-j|\in D$. A characterization of the degree sequences of tight distance graphs is given. This characterization yields a fast method for recognizing and realizing degree sequences of tight distance graphs.     

Chromatic Numbers of Some Distance Graphs

Mathematical Notes - For positive integers n > r > s, G(n, r, s) is the graph whose vertices are the r-element subsets of an n-element set, two subsets being adjacent if their...