Source author record

Meiqin Wei

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT Discrete Mathematics

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Distance proper connection of graphs

Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called a distance $\ell$ -proper path if no two edges of the same color appear with fewer than $\ell$ edges in between on $P$ . The graph $G$ is called $(k,\ell)$ -proper connected if every pair of distinct vertices of $G$ are connected by $k$ pairwise internally vertex-disjoint distance $\ell$ -proper paths in $G$ . For a $k$ -connected graph $G$ , the minimum number of colors needed to make $G$ $(k,\ell)$ -proper connected is called the $(k,\ell)$ -proper connection number of $G$ and denoted by $pc_{k,\ell}(G)$ . In this paper, we prove that $pc_{1,2}(G)\leq 5$ for any $2$ -connected graph $G$ . Considering graph operations, we find that $3$ is a sharp upper bound for the $(1,2)$ -proper connection number of the join and the Cartesian product of almost all graphs. In addition, we find some basic properties of the $(k,\ell)$ -proper connection number and determine the values of $pc_{1,\ell}(G)$ where $G$ is a traceable graph, a tree, a complete bipartite graph, a complete multipartite graph, a wheel, a cube or a permutation graph of a nontrivial traceable graph.

preprint2016arXiv

Distance proper connection of graphs and their complements

Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called a distance $\ell$ -proper path if no two edges of the same color can appear with less than $\ell$ edges in between on $P$ . The graph $G$ is called $(k,\ell)$ -proper connected if there is an edge-coloring such that every pair of distinct vertices of $G$ are connected by $k$ pairwise internally vertex-disjoint distance $\ell$ -proper paths in $G$ . The minimum number of colors needed to make $G$ $(k,\ell)$ -proper connected is called the $(k,\ell)$ -proper connection number of $G$ and denoted by $pc_{k,\ell}(G)$ . In this paper we first focus on the $(1,2)$ -proper connection number of $G$ depending on some constraints of $\overline G$ . Then, we characterize the graphs of order $n$ with $(1,2)$ -proper connection number $n-1$ or $n-2$ . Using this result, we investigate the Nordhaus-Gaddum-Type problem of $(1,2)$ -proper connection number and prove that $pc_{1,2}(G)+pc_{1,2}(\overline{G})\leq n+2$ for connected graphs $G$ and $\overline{G}$ . The equality holds if and only if $G$ or $\overline{G}$ is isomorphic to a double star.

preprint2015arXiv

A survey of recent results in (generalized) graph entropies

The entropy of a graph was first introduced by Rashevsky \cite{Rashevsky} and Trucco \cite{Trucco} to interpret as the structural information content of the graph and serve as a complexity measure. In this paper, we first state a number of definitions of graph entropy measures and generalized graph entropies. Then we survey the known results about them from the following three respects: inequalities and extremal properties on graph entropies, relationships between graph structures, graph energies, topological indices and generalized graph entropies, complexity for calculation of graph entropies. Various applications of graph entropies together with some open problems and conjectures are also presented for further research.

preprint2015arXiv

Proper connection number and connected dominating sets

The proper connection number $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one path in $G$ such that no two adjacent edges of the path are colored the same, and such a path is called a proper path. In this paper, we show that for every connected graph with diameter 2 and minimum degree at least 2, its proper connection number is 2. Then, we give an upper bound $\frac{3n}{δ+ 1}-1$ for every connected graph of order $n$ and minimum degree $δ$ . We also show that for every connected graph $G$ with minimum degree at least $2$ , the proper connection number $pc(G)$ is upper bounded by $pc(G[D])+2$ , where $D$ is a connected two-way (two-step) dominating set of $G$ . Bounds of the form $pc(G)\leq 4$ or $pc(G)=2$ , for many special graph classes follow as easy corollaries from this result, which include connected interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs and chain graphs, all with minimum degree at least $2$ . Furthermore, we get the sharp upper bound 3 for the proper connection numbers of interval graphs and circular arc graphs through analyzing their structures.

preprint2014arXiv

Additive codes over $GF(4)$ from circulant graphs

In $2006$ , Danielsen and Parker \cite{DP} proved that every self-dual additive code over $GF(4)$ is equivalent to a graph code. So, graph is an important tool for searching (proposed) optimum codes. In this paper, we introduce a new method of searching (proposed) optimum additive codes from circulant graphs.

preprint2014arXiv

Formally self-dual linear binary codes from circulant graphs

In 2002, Tonchev first constructed some linear binary codes defined by the adjacency matrices of undirected graphs. So, graph is an important tool for searching optimum codes. In this paper, we introduce a new method of searching (proposed) optimum formally self-dual linear binary codes from circulant graphs.

preprint2014arXiv

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

The entropy of a graph is an information-theoretic quantity which expresses the complexity of a graph \cite{DM1,M}. After Shannon introduced the definition of entropy to information and communication, many generalizations of the entropy measure have been proposed, such as Rényi entropy and Daròczy's entropy. In this article, we prove accurate connections (inequalities) between generalized graph entropies, distinct graph energies and topological indices. Additionally, we obtain some extremal properties of nine generalized graph entropies by employing distinct graph energies and topological indices.

preprint2014arXiv

On a conjecture about tricyclic graphs with maximal energy

For a given simple graph $G$ , the energy of $G$ , denoted by $\mathcal {E}(G)$ , is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix, which was defined by I. Gutman. The problem on determining the maximal energy tends to be complicated for a given class of graphs. There are many approaches on the maximal energy of trees, unicyclic graphs and bicyclic graphs, respectively. Let $P^{6,6,6}_n$ denote the graph with $n\geq 20$ vertices obtained from three copies of $C_6$ and a path $P_{n-18}$ by adding a single edge between each of two copies of $C_6$ to one endpoint of the path and a single edge from the third $C_6$ to the other endpoint of the $P_{n-18}$ . Very recently, Aouchiche et al. [M. Aouchiche, G. Caporossi, P. Hansen, Open problems on graph eigenvalues studied with AutoGraphiX, {\it Europ. J. Comput. Optim.} {\bf 1}(2013), 181--199] put forward the following conjecture: Let $G$ be a tricyclic graphs on $n$ vertices with $n=20$ or $n\geq22$ , then $\mathcal{E}(G)\leq \mathcal{E}(P_{n}^{6,6,6})$ with equality if and only if $G\cong P_{n}^{6,6,6}$ . Let $G(n;a,b,k)$ denote the set of all connected bipartite tricyclic graphs on $n$ vertices with three vertex-disjoint cycles $C_{a}$ , $C_{b}$ and $C_{k}$ , where $n\geq 20$ . In this paper, we try to prove that the conjecture is true for graphs in the class $G\in G(n;a,b,k)$ , but as a consequence we can only show that this is true for most of the graphs in the class except for 9 families of such graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Meiqin Wei

Research overview

Is this your work?

8 publications

Distance proper connection of graphs

Distance proper connection of graphs and their complements

A survey of recent results in (generalized) graph entropies

Proper connection number and connected dominating sets

Additive codes over $GF(4)$ from circulant graphs

Formally self-dual linear binary codes from circulant graphs

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

On a conjecture about tricyclic graphs with maximal energy

See the researcher in context

Building this map preview

Meiqin Wei

Research overview

Is this your work?

8 publications

Distance proper connection of graphs

Distance proper connection of graphs and their complements

A survey of recent results in (generalized) graph entropies

Proper connection number and connected dominating sets

Additive codes over GF(4)GF(4)GF(4) from circulant graphs

Formally self-dual linear binary codes from circulant graphs

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

On a conjecture about tricyclic graphs with maximal energy

See the researcher in context

Building this map preview

Additive codes over $GF(4)$ from circulant graphs