BZPEER

preprint2020arXiv

Asymptotic values of four Laplacian-type energies for matrices with degree-distance-based entries of random graphs

Let $f(D(i, j), d_i, d_j)$ be a real function symmetric in $i$ and $j$ with the property that $f(d, (1+o(1))np, (1+o(1))np)=(1+o(1))f(d, np, np)$ for $d=1,2$ . Let $G$ be a graph, $d_i$ denote the degree of a vertex $i$ of $G$ and $D(i, j)$ denote the distance between vertices $i$ and $j$ in $G$ . In this paper, we define the $f$ -weighted Laplacian matrix for random graphs in the Erd $\ddot{o}$ s-R $\acute{e}$ nyi random graph model $\mathcal{G}_{n, p}$ , where $p\in (0, 1)$ is fixed. Four weighted Laplacian type energies: the weighted Laplacian energy $\mathscr{LE}_f(G)$ , weighted signless Laplacian energy $\mathscr{LE}^{+}_f(G)$ , weighted incidence energy $\mathscr{IE}_f(G)$ and the weighted Laplacian-energy like invariant $\mathscr{LEL}_f(G)$ are introduced and studied. We obtain the asymptotic values of $\mathscr{IE}_f(G)$ and $\mathscr{LEL}_f(G)$ , and the values of $\mathscr{LE}_f(G)$ and $\mathscr{LE}_f^{+}(G)$ under the condition that $f(D(i, j), d_i, d_j)$ is a function dependent only on $D(i, j)$ . As a consequence, we get that for almost all graphs $G_p\in \mathcal{G}_{n, p}$ , the energy for the matrix with degree-distance-based entries of $G_p$ , $\mathscr{E}(W_f(G_p)) < \mathscr{LE}_f(G_p),$ the Laplacian energy of the matrix, which is a generalization of a conjecture by Gutman et al.

preprint2020arXiv

Bounds for the rainbow disconnection number of graphs

An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, there exists a $u$ - $v$ -rainbow-cut separating them. For a connected graph $G$ , the rainbow disconnection number of $G$ , denoted by rd $(G)$ , is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we first give some tight upper bounds for rd $(G)$ , and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $λ^+(G)\leq \textnormal{rd}(G)\leq λ^+(G)+1$ , where $λ^+(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd $(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd $(L(G))$ of the line graph $L(G)$ of $G$ .

preprint2020arXiv

Complexity results for two kinds of colored disconnections of graphs

The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. in 2018. Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is $NP$ -complete to decide whether a given edge-colored graph $G$ with maximum degree $Δ(G)=4$ is proper disconnected. Then, for a graph $G$ with $Δ(G)\leq 3$ we show that $pd(G)\leq 2$ and determine the graphs with $pd(G)=1$ and $2$ , respectively. Furthermore, we show that for a general graph $G$ , deciding whether $pd(G)=1$ is $NP$ -complete, even if $G$ is bipartite. We also show that it is $NP$ -complete to decide whether a given vertex-colored graph $G$ is rainbow vertex-disconnected, even though the graph $G$ has $Δ(G)=3$ or is bipartite.

preprint2020arXiv

Further results on the rainbow vertex-disconnection of graphs

Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called \emph{rainbow vertex-disconnected} if for any two vertices $x$ and $y$ of $G$ , there exists a vertex subset $S$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$ ; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$ . Such a vertex subset $S$ is called a \emph{rainbow vertex-cut} of $G$ . For a connected graph $G$ , the \emph{rainbow vertex-disconnection number} of $G$ , denoted by $rvd(G)$ , is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we obtain bounds of the rainbow vertex-disconnection number of a graph in terms of the minimum degree and maximum degree of the graph. We give a tighter upper bound for the maximum size of a graph $G$ with $rvd(G)=k$ for $k\geq\frac{n}{2}$ . We then characterize the graphs of order $n$ with rainbow vertex-disconnection number $n-1$ and obtain the maximum size of a graph $G$ with $rvd(G)=n-1$ . Moreover, we get a sharp threshold function for the property $rvd(G(n,p))=n$ and prove that almost all graphs $G$ have $rvd(G)=rvd(\overline{G})=n$ . Finally, we obtain some Nordhaus-Gaddum-type results: $n-5\leq rvd(G)+rvd(\overline{G})\leq 2n$ and $n-1\leq rvd(G)\cdot rvd(\overline{G})\leq n^2$ for the rainbow vertex-disconnection numbers of nontrivial connected graphs $G$ and $\overline{G}$ with order $n\geq 24$ .

preprint2020arXiv

Graph colorings under global structural conditions

More than ten years ago in 2008, a new kind of graph coloring appeared in graph theory, which is the {\it rainbow connection coloring} of graphs, and then followed by some other new concepts of graph colorings, such as {\it proper connection coloring, monochromatic connection coloring, and conflict-free connection coloring} of graphs. In about ten years of our consistent study, we found that these new concepts of graph colorings are actually quite different from the classic graph colorings. These {\it colored connection colorings} of graphs are brand-new colorings and they need to take care of global structural properties (for example, connectivity) of a graph under the colorings; while the traditional colorings of graphs are colorings under which only local structural properties (adjacent vertices or edges) of a graph are taken care of. Both classic colorings and the new colored connection colorings can produce the so-called chromatic numbers. We call the colored connection numbers the {\it global chromatic numbers}, and the classic or traditional chromatic numbers the {\it local chromatic numbers}. This paper intends to clarify the difference between the colored connection colorings and the traditional colorings, and finally to propose the new concepts of global colorings under which global structural properties of the colored graph are kept, and the global chromatic numbers.

preprint2020arXiv

Group Connectivity under $3$ -Edge-Connectivity

Let $S,T$ be two distinct finite Abelian groups with $|S|=|T|$ . A fundamental theorem of Tutte shows that a graph admits a nowhere-zero $S$ -flow if and only if it admits a nowhere-zero $T$ -flow. Jaeger, Linial, Payan and Tarsi in 1992 introduced group connectivity as an extension of flow theory, and they asked whether such a relation holds for group connectivity analogy. It was negatively answered by Hušek, Mohelníková and Šámal in 2017 for graphs with edge-connectivity 2 for the groups $S=\mathbb{Z}_4$ and $T=\mathbb{Z}_2^2$ . In this paper, we extend their results to $3$ -edge-connected graphs (including both cubic and general graphs), which answers open problems proposed by Hušek, Mohelníková and Šámal(2017) and Lai, Li, Shao and Zhan(2011). Combining some previous results, this characterizes all the equivalence of group connectivity under $3$ -edge-connectivity, showing that every $3$ -edge-connected $S$ -connected graph is $T$ -connected if and only if $\{S,T\}\neq \{\mathbb{Z}_4,\mathbb{Z}_2^2\}$ .

preprint2020arXiv

Hardness results for three kinds of colored connections of graphs

The concept of rainbow connection number of a graph was introduced by Chartrand et al. in 2008. Inspired by this concept, other concepts on colored version of connectivity in graphs were introduced, such as the monochromatic connection number by Caro and Yuster in 2011, the proper connection number by Borozan et al. in 2012, and the conflict-free connection number by Czap et al. in 2018, as well as some other variants of connection numbers later on. Chakraborty et al. proved that to compute the rainbow connection number of a graph is NP-hard. For a long time, it has been tried to fix the computational complexity for the monochromatic connection number, the proper connection number and the conflict-free connection number of a graph. However, it has not been solved yet. Only the complexity results for the strong version, i.e., the strong proper connection number and the strong conflict-free connection number, of these connection numbers were determined to be NP-hard. In this paper, we prove that to compute each of the monochromatic connection number, the proper connection number and the conflict free connection number for a graph is NP-hard. This solves a long standing problem in this field, asked in many talks of workshops and papers.

preprint2020arXiv

Monochromatic disconnection: Erdős-Gallai-type problems and product graphs

For an edge-colored graph $G$ , we call an edge-cut $M$ of $G$ monochromatic if the edges of $M$ are colored with a same color. The graph $G$ is called monochromatically disconnected if any two distinct vertices of $G$ are separated by a monochromatic edge-cut. The monochromatic disconnection number, denoted by $md(G)$ , of a connected graph $G$ is the maximum number of colors that are allowed to make $G$ monochromatically disconnected. In this paper, we solve the Erdős-Gallai-type problems for the monochromatic disconnection, and give the monochromatic disconnection numbers for four graph products, i.e., Cartesian, strong, lexicographic, and tensor products.

preprint2020arXiv

Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles

In an edge-colored graph $(G,c)$ , let $d^c(v)$ denote the number of colors on the edges incident with a vertex $v$ of $G$ and $δ^c(G)$ denote the minimum value of $d^c(v)$ over all vertices $v\in V(G)$ . A cycle of $(G,c)$ is called proper if any two adjacent edges of the cycle have distinct colors. An edge-colored graph $(G,c)$ on $n\geq 3$ vertices is called properly vertex-pancyclic if each vertex of $(G,c)$ is contained in a proper cycle of length $\ell$ for every $\ell$ with $3 \le \ell \le n$ . Fujita and Magnant conjectured that every edge-colored complete graph on $n\geq 3$ vertices with $δ^c(G)\geq \frac{n+1}{2}$ is properly vertex-pancyclic. Chen, Huang and Yuan partially solve this conjecture by adding an extra condition that $(G,c)$ does not contain any monochromatic triangle. In this paper, we show that this conjecture is true if the edge-colored complete graph contain no joint monochromatic triangles.

preprint2020arXiv

Rainbow monochromatic $k$ -edge-connection colorings of graphs

A path in an edge-colored graph is called a monochromatic path if all edges of the path have a same color. We call $k$ paths $P_1,\cdots,P_k$ rainbow monochromatic paths if every $P_i$ is monochromatic and for any two $i\neq j$ , $P_i$ and $P_j$ have different colors. An edge-coloring of a graph $G$ is said to be a rainbow monochromatic $k$ -edge-connection coloring (or $RMC_k$ -coloring for short) if every two distinct vertices of $G$ are connected by at least $k$ rainbow monochromatic paths. We use $rmc_k(G)$ to denote the maximum number of colors that ensures $G$ has an $RMC_k$ -coloring, and this number is called the rainbow monochromatic $k$ -edge-connection number. We prove the existence of $RMC_k$ -colorings of graphs, and then give some bounds of $rmc_k(G)$ and present some graphs whose $rmc_k(G)$ reaches the lower bound. We also obtain the threshold function for $rmc_k(G(n,p))\geq f(n)$ , where $\lfloor\frac{n}{2}\rfloor> k\geq 1$ .

preprint2020arXiv

Strong rainbow disconnection in graphs

Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$ is called a {\it rainbow edge-cut} if no two edges of $R$ are colored with the same color. For two distinct vertices $u$ and $v$ of $G$ , if an edge-cut separates them, then the edge-cut is called a {\it $u$ - $v$ -edge-cut}. An edge-colored graph $G$ is called \emph{strong rainbow disconnected} if for every two distinct vertices $u$ and $v$ of $G$ , there exists a both rainbow and minimum $u$ - $v$ -edge-cut ({\it rainbow minimum $u$ - $v$ -edge-cut} for short) in $G$ , separating them, and this edge-coloring is called a {\it strong rainbow disconnection coloring} (srd-{\it coloring} for short) of $G$ . For a connected graph $G$ , the \emph{strong rainbow disconnection number} (srd-{\it number} for short) of $G$ , denoted by $\textnormal{srd}(G)$ , is the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. In this paper, we first characterize the graphs with $m$ edges such that $\textnormal{srd}(G)=k$ for each $k \in \{1,2,m\}$ , respectively, and we also show that the srd-number of a nontrivial connected graph $G$ equals the maximum srd-number among the blocks of $G$ . Secondly, we study the srd-numbers for the complete $k$ -partite graphs, $k$ -edge-connected $k$ -regular graphs and grid graphs. Finally, we show that for a connected graph $G$ , to compute $\textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already NP-complete to decide if $\textnormal{srd}(G)=3$ for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong rainbow disconnected.

preprint2020arXiv

The asymptotic value of energy for matrices with degree-distance-based entries of random graphs

For a graph $G=(V, E)$ and $i, j\in V$ , denote the distance between $i$ and $j$ in $G$ by $D(i, j)$ and the degrees of $i$ , $j$ by $d_i$ , $d_j$ , respectively. Let $f(D(i, j), d_{i}, d_{j})$ be a function symmetric in $i$ and $j$ . Define a matrix $W_f(G)$ , called the weighted distance matrix, of $G$ , with the $ij$ -entry $W_f(G)(i, j)=f(D(i, j), d_{i}, d_{j})$ if $i\neq j$ and $W_f(G)(i, j)=0$ if $i=j$ . In this paper, we prove that if the symmetric function $f$ satisfies that $f(D(i, j), (1+o(1))np, (1+o(1))np)=(1+o(1))f(D(i, j), np, np)$ , then for almost all graphs $G_p$ in the $Erd\ddot{o}s$ - $R\acute{e}nyi$ random graph model $\mathcal{G}_{n, p}$ , the energy of $W_f(G_p)$ is $\{(\frac{8}{3π}\sqrt{p(1-p)}+o(1))\cdot|f(1, np, np)-f(2, np, np)|+o(|f(2, np, np)|)\}\cdot n^{3/2}$ . As a consequence, we give the asymptotic values of energies of a variety of weighted distance matrices with function $f$ from distance-based only and mixed with degree-distance-based topological indices of chemical use. This generalizes our former result with only degree-based weights.

preprint2020arXiv

The asymptotic value of graph energy for random graphs with degree-based weights

In this paper, we investigate the energy of a weighted random graph $G_p(f)$ in $G_{n,p}(f)$ , in which each edge $ij$ takes the weight $f(d_i,d_j)$ , where $d_v$ is a random variable, the degree of vertex $v$ in the random graph $G_p$ of the Erdös--Rényi random graph model $G_{n,p}$ , and $f$ is a symmetric real function on two variables. Suppose $|f(d_i,d_j)|\leq C n^m$ for some constants $C, m>0$ , and $f((1+o(1))np,(1+o(1))np)=(1+o(1))f(np,np)$ . Then, for almost all graphs $G_p(f)$ in $G_{n,p}(f)$ , the energy of $G_p(f)$ is $(1+o(1))f(np,np)\frac{8}{3π}\sqrt{p(1-p)}\cdot n^{3/2},$ where $p\in(0,1)$ is any fixed and independent of $n$ . Consequently, with this one basket we can get the asymptotic values of various kinds of graph energies of chemical use, such as Randić energy, ABC energy, and energies of random matrices obtained from various kinds of degree-based chemical indices.

preprint2020arXiv

The rainbow vertex-disconnection in graphs

Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called \emph{rainbow vertex-disconnected} if for any two vertices $x$ and $y$ of $G$ , there exists a vertex subset $S$ of $G$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$ ; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$ . For a connected graph $G$ , the \emph{rainbow vertex-disconnection number} of $G$ , denoted by $rvd(G)$ , is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we characterize all graphs of order $n$ with rainbow vertex-disconnection number $k$ for $k\in\{1,2,n\}$ , and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph $G$ with order $n$ and $rvd(G)=k$ for given integers $k$ and $n$ with $1\leq k\leq n$ .

preprint2020arXiv

Upper bounds for the $MD$ -numbers and characterization of extremal graphs

For an edge-colored graph $G$ , we call an edge-cut $M$ of $G$ monochromatic if the edges of $M$ are colored with the same color. The graph $G$ is called monochromatic disconnected if any two distinct vertices of $G$ are separated by a monochromatic edge-cut. For a connected graph $G$ , the monochromatic disconnection number (or $MD$ -number for short) of $G$ , denoted by $md(G)$ , is the maximum number of colors that are allowed in order to make $G$ monochromatic disconnected. For graphs with diameter one, they are complete graphs and so their $MD$ -numbers are $1$ . For graphs with diameter at least 3, we can construct $2$ -connected graphs such that their $MD$ -numbers can be arbitrarily large; whereas for graphs $G$ with diameter two, we show that if $G$ is a $2$ -connected graph then $md(G)\leq 2$ , and if $G$ has a cut-vertex then $md(G)$ is equal to the number of blocks of $G$ . So, we will focus on studying $2$ -connected graphs with diameter two, and give two upper bounds of their $MD$ -numbers depending on their connectivity and independent numbers, respectively. We also characterize the $\left\lfloor\frac{n}{2}\right\rfloor$ -connected graphs (with large connectivity) whose $MD$ -numbers are $2$ and the $2$ -connected graphs (with small connectivity) whose $MD$ -numbers archive the upper bound $\left\lfloor\frac{n}{2}\right\rfloor.$ For graphs with connectivity less than $\frac n 2$ , we show that if the connectivity of a graph is in linear with its order $n$ , then its $MD$ -number is upper bounded by a constant, and this suggests us to leave a conjecture that for a $k$ -connected graph $G$ , $md(G)\leq \left\lfloor\frac{n}{k}\right\rfloor$ .

preprint2016arXiv

3-Rainbow index and forbidden subgraphs

A tree in an edge-colored connected graph $G$ is called \emph{a rainbow tree} if no two edges of it are assigned the same color. For a vertex subset $S\subseteq V(G)$ , a tree is called an \emph{ $S$ -tree} if it connects $S$ in $G$ . A \emph{ $k$ -rainbow coloring} of $G$ is an edge-coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$ , there exists a rainbow $S$ -tree in $G$ . The minimum number of colors that are needed in a $k$ -rainbow coloring of $G$ is the \emph{ $k$ -rainbow index} of $G$ , denoted by $rx_k(G)$ . The \emph{Steiner distance $d(S)$ } of a set $S$ of vertices of $G$ is the minimum size of an $S$ -tree $T$ . The \emph{ $k$ -Steiner diameter $sdiam_k(G)$ } of $G$ is defined as the maximum Steiner distance of $S$ among all sets $S$ with $k$ vertices of $G$ . In this paper, we focus on the 3-rainbow index of graphs and find all finite families $\mathcal{F}$ of connected graphs, for which there is a constant $C_\mathcal{F}$ such that, for every connected $\mathcal{F}$ -free graph $G$ , $rx_3(G)\leq sdiam_3(G)+C_\mathcal{F}$ .

preprint2016arXiv

A Source-level Energy Optimization Framework for Mobile Applications

Energy efficiency can have a significant influence on user experience of mobile devices such as smartphones and tablets. Although energy is consumed by hardware, software optimization plays an important role in saving energy, and thus software developers have to participate in the optimization process. The source code is the interface between the developer and hardware resources. In this paper, we propose an energy-optimization framework guided by a source code energy model that allows developers to be aware of energy usage induced by the code and to apply very targeted source-level refactoring strategies. The framework also lays a foundation for the code optimization by automatic tools. To the best of our knowledge, our work is the first that achieves this for a high-level language such as Java. In a case study, the experimental evaluation shows that our approach is able to save from 6.4% to 50.2% of the CPU energy consumption in various application scenarios.

preprint2016arXiv

An Energy-Aware Programming Approach for Mobile Application Development Guided by a Fine-Grained Energy Model

Energy efficiency has a significant influence on user experience of battery-driven devices such as smartphones and tablets. It is shown that software optimization plays an important role in reducing energy consumption of system. However, in mobile devices, the conventional nature of compiler considers not only energy-efficiency but also limited memory usage and real-time response to user inputs, which largely limits the compiler's positive impact on energy-saving. As a result, the code optimization relies more on developers. In this paper, we propose an energy-aware programming approach, which is guided by an operation-based source-code-level energy model. And this approach is placed at the end of software engineering life cycle to avoid distracting developers from guaranteeing the correctness of system. The experimental result shows that our approach is able to save from 6.4% to 50.2% of the overall energy consumption depending on different scenarios.

preprint2016arXiv

Degree sum conditions for graphs to have proper connection number 2

A path $P$ in an edge-colored graph $G$ is a \emph{proper path} if no two adjacent edges of $P$ are colored with the same color. The graph $G$ is \emph{proper connected} if, between every pair of vertices, there exists a proper path in $G$ . The \emph{proper connection number} $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors to make $G$ proper connected. In this paper, we study the degree sum condition for a general graph or a bipartite graph to have proper connection number 2. First, we show that if $G$ is a connected noncomplete graph of order $n\geq 5$ such that $d(x)+d(y)\geq \frac{n}{2}$ for every pair of nonadjacent vertices $x,y\in V(G)$ , then $pc(G)=2$ except for three small graphs on 6, 7 and 8 vertices. In addition, we obtain that if $G$ is a connected bipartite graph of order $n\geq 4$ such that $d(x)+d(y)\geq \frac{n+6}{4}$ for every pair of nonadjacent vertices $x,y\in V(G)$ , then $pc(G)=2$ . Examples are given to show that the above conditions are best possible.

preprint2016arXiv

Derivatives and real roots of graph polynomials

Graph polynomials are polynomials assigned to graphs. Interestingly, they also arise in many areas outside graph theory as well. Many properties of graph polynomials have been widely studied. In this paper, we survey some results on the derivative and real roots of graph polynomials, which have applications in chemistry, control theory and computer science. Related to the derivatives of graph polynomials, polynomial reconstruction of the matching polynomial is also introduced.

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.

preprint2016arXiv

ENTRA: Whole-Systems Energy Transparency

Promoting energy efficiency to a first class system design goal is an important research challenge. Although more energy-efficient hardware can be designed, it is software that controls the hardware; for a given system the potential for energy savings is likely to be much greater at the higher levels of abstraction in the system stack. Thus the greatest savings are expected from energy-aware software development, which is the vision of the EU ENTRA project. This article presents the concept of energy transparency as a foundation for energy-aware software development. We show how energy modelling of hardware is combined with static analysis to allow the programmer to understand the energy consumption of a program without executing it, thus enabling exploration of the design space taking energy into consideration. The paper concludes by summarising the current and future challenges identified in the ENTRA project.

preprint2016arXiv

Erdős-Gallai-type results for total monochromatic connection of graphs

A graph is said to be {\it total-colored} if all the edges and the vertices of the graph are colored. A total-coloring of a graph is a {\it total monochromatically-connecting coloring} ({\it TMC-coloring}, for short) if any two vertices of the graph are connected by a path whose edges and internal vertices have the same color. For a connected graph $G$ , the {\it total monochromatic connection number}, denoted by $tmc(G)$ , is defined as the maximum number of colors used in a TMC-coloring of $G$ . In this paper, we study two kinds of Erdős-Gallai-type problems for $tmc(G)$ and completely solve them.

preprint2016arXiv

Fine-Grained Energy Modeling for the Source Code of a Mobile Application

Energy efficiency has a significant influence on user experience of battery-driven devices such as smartphones and tablets. The goal of an energy model for source code is to lay a foundation for the application of energy-saving techniques during software development. The challenge is to relate hardware energy consumption to high-level application code, considering the complex run-time context and software stack. Traditional techniques build the energy model by mapping a hardware energy model onto software constructs; this approach faces obstacles when the software stack consists of a number of abstract layers. Another approach that has been followed is to utilize hardware or operating system features to estimate software energy information at a coarse level of granularity such as blocks, methods or even applications. In this paper, we explain how to construct a fine-grained energy model for the source code, which is based on "energy operations" identified directly from the source code and able to provide more valuable information for code optimization. We apply the approach to a class of applications based on a game-engine, and explain the wider applicability of the method.

preprint2016arXiv

More on total monochromatic connection of graphs

A graph is said to be {\it total-colored} if all the edges and the vertices of the graph are colored. A total-coloring of a graph is a {\it total monochromatically-connecting coloring} ({\it TMC-coloring}, for short) if any two vertices of the graph are connected by a path whose edges and internal vertices on the path have the same color. For a connected graph $G$ , the {\it total monochromatic connection number}, denoted by $tmc(G)$ , is defined as the maximum number of colors used in a TMC-coloring of $G$ . Note that a TMC-coloring does not exist if $G$ is not connected, in which case we simply let $tmc(G)=0$ . In this paper, we first characterize all graphs of order $n$ and size $m$ with $tmc(G)=3,4,5,6,m+n-2,m+n-3$ and $m+n-4$ , respectively. Then we determine the threshold function for a random graph to have $tmc(G)\geq f(n)$ , where $f(n)$ is a function satisfying $1\leq f(n)<\frac{1}{2}n(n-1)+n$ . Finally, we show that for a given connected graph $G$ , and a positive integer $L$ with $L\leq m+n$ , it is NP-complete to decide whether $tmc(G)\geq L$ .

preprint2016arXiv

Nordhaus-Gaddum-type theorem for total proper connection number of graphs

A graph is said to be \emph{total-colored} if all the edges and the vertices of the graph are colored. A path $P$ in a total-colored graph $G$ is called a \emph{total-proper path} if $(i)$ any two adjacent edges of $P$ are assigned distinct colors; $(ii)$ any two adjacent internal vertices of $P$ are assigned distinct colors; $(iii)$ any internal vertex of $P$ is assigned a distinct color from its incident edges of $P$ . The total-colored graph $G$ is \emph{total-proper connected} if any two distinct vertices of $G$ are connected by a total-proper path. The \emph{total-proper connection number} of a connected graph $G$ , denoted by $tpc(G)$ , is the minimum number of colors that are required to make $G$ total-proper connected. In this paper, we first characterize the graphs $G$ on $n$ vertices with $tpc(G)=n-1$ . Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if $G$ and $\overline{G}$ are connected complementary graphs on $n$ vertices, then $6\leq tpc(G)+tpc(\overline{G})\leq n+2$ . Examples are given to show that the lower bound is sharp for $n\geq 4$ . The upper bound is reached for $n\geq 5$ if and only if $G$ or $\overline{G}$ is the tree with maximum degree $n-2$ .

preprint2016arXiv

On two conjectures about the proper connection number of graphs

A path in an edge-colored graph is called proper if no two consecutive edges of the path receive the same color. For a connected graph $G$ , the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges so that every pair of distinct vertices of $G$ are connected by at least one proper path in $G$ . In this paper, we consider two conjectures on the proper connection number of graphs. The first conjecture states that if $G$ is a noncomplete graph with connectivity $κ(G) = 2$ and minimum degree $δ(G)\ge 3$ , then $pc(G) = 2$ , posed by Borozan et al.~in [Discrete Math. 312(2012), 2550-2560]. We give a family of counterexamples to disprove this conjecture. However, from a result of Thomassen it follows that 3-edge-connected noncomplete graphs have proper connection number 2. Using this result, we can prove that if $G$ is a 2-connected noncomplete graph with $diam(G)=3$ , then $pc(G) = 2$ , which solves the second conjecture we want to mention, posed by Li and Magnant in [Theory \& Appl. Graphs 0(1)(2015), Art.2].

preprint2016arXiv

Rainbow vertex-connection and forbidden subgraphs

A path in a vertex-colored graph is called \emph{vertex-rainbow} if its internal vertices have pairwise distinct colors. A graph $G$ is \emph{rainbow vertex-connected} if for any two distinct vertices of $G$ , there is a vertex-rainbow path connecting them. For a connected graph $G$ , the \emph{rainbow vertex-connection number} of $G$ , denoted by $rvc(G)$ , is defined as the minimum number of colors that are required to make $G$ rainbow vertex-connected. In this paper, we find all the families $\mathcal{F}$ of connected graphs with $|\mathcal{F}|\in\{1,2\}$ , for which there is a constant $k_\mathcal{F}$ such that, for every connected $\mathcal{F}$ -free graph $G$ , $rvc(G)\leq diam(G)+k_\mathcal{F}$ , where $diam(G)$ is the diameter of $G$ .

preprint2016arXiv

Solution to a conjecture on the proper connection number of graphs

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph $G$ , the proper connection number $pc(G)$ of $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 proper path in $G$ . Recently, Li and Magnant in [Theory Appl. Graphs 0(1)(2015), Art.2] posed the following conjecture: If $G$ is a connected noncomplete graph of order $n \geq 5$ and minimum degree $δ(G) \geq n/4$ , then $pc(G)=2$ . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if $G$ is a connected bipartite graph of order $n\geq 4$ with $δ(G)\geq \frac{n+6}{8}$ , then $pc(G)=2$ .

preprint2016arXiv

Solutions for two conjectures on kaleidoscopic edge-colorings

For an $r$ -regular graph $G$ , we define an edge-coloring $c$ with colors from $\{1,2,\cdots,$ $k\}$ , in such a way that any vertex of $G$ is incident to at least one edge of each color. The multiset-color $c_m(v)$ of a vertex $v$ is defined as the ordered tuple $(a_1,a_2,\cdots ,a_k)$ , where $a_i \ (1\leq i\leq k)$ denotes the number of edges with color $i$ which are incident with $v$ in $G$ . Then this edge-coloring $c$ is called a {\it $k$ -kaleidoscopic coloring} of $G$ if every two distinct vertices in $G$ have different multiset-colors and in this way the graph $G$ is defined as a {\it $k$ -kaleidoscope}. In this paper, we determine the integer $k$ for a complete graph $K_n$ to be a $k$ -kaleidoscope, and hence solve a conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, Springer, New York, 2016] that for any integers $n$ and $k$ with $n\geq k+3 \geq 6$ , the complete graph $K_n$ is a $k$ -kaleidoscope. Then, we construct an $r$ -regular $3$ -kaleidoscope of order $\binom{r-1}{2}-1$ for each integer $r\geq 7$ , where $r\equiv 3\ (\text{mod}\ 4)$ , which solves another conjecture in the same book on the maximum order for $r$ -regular $3$ -kaleidoscopes.

preprint2016arXiv

Some upper bounds for the $3$ -proper index of graphs

A tree $T$ in an edge-colored graph is a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be a fixed integer with $2\le k\le n$ . For a vertex subset $S \subseteq V(G)$ with $\left|S\right| \ge 2$ , a tree containing all the vertices of $S$ in $G$ is called an $S$ -tree. An edge-coloring of $G$ is called a \emph{ $k$ -proper coloring} if for every $k$ -subset $S$ of $V(G)$ , there exists a proper $S$ -tree in $G$ . For a connected graph $G$ , the \emph{ $k$ -proper index} of $G$ , denoted by $px_k(G)$ , is the smallest number of colors that are needed in a $k$ -proper coloring of $G$ . In this paper, we show that for every connected graph $G$ of order $n$ and minimum degree $δ\geq 3$ , $px_{3}(G)\le n\frac{\ln(δ+1)}{δ+1}(1+o_δ(1))+2$ . We also prove that for every connected graph $G$ with minimum degree at least $3$ , $px_{3}(G) \le px_{3}(G[D])+3$ when $D$ is a connected $3$ -way dominating set of $G$ and $px_{3}(G) \le px_{3}(G[D])+1$ when $D$ is a connected $3$ -dominating set of $G$ . In addition, we obtain tight upper bounds of the 3-proper index for two special graph classes: threshold graphs and chain graphs. Finally, we prove that $px_3(G) \le \lfloor\frac{n}{2}\rfloor$ for any 2-connected graphs with at least four vertices.

preprint2016arXiv

The (vertex-)monochromatic index of a graph

A tree $T$ in an edge-colored graph $H$ is called a \emph{monochromatic tree} if all the edges of $T$ have the same color. For $S\subseteq V(H)$ , a \emph{monochromatic $S$ -tree} in $H$ is a monochromatic tree of $H$ containing the vertices of $S$ . For a connected graph $G$ and a given integer $k$ with $2\leq k\leq |V(G)|$ , the \emph{ $k$ -monochromatic index $mx_k(G)$ } of $G$ is the maximum number of colors needed such that for each subset $S\subseteq V(G)$ of $k$ vertices, there exists a monochromatic $S$ -tree. In this paper, we prove that for any connected graph $G$ , $mx_k(G)=|E(G)|-|V(G)|+2$ for each $k$ such that $3\leq k\leq |V(G)|$ . A tree $T$ in a vertex-colored graph $H$ is called a \emph{vertex-monochromatic tree} if all the internal vertices of $T$ have the same color. For $S\subseteq V(H)$ , a \emph{vertex-monochromatic $S$ -tree} in $H$ is a vertex-monochromatic tree of $H$ containing the vertices of $S$ . For a connected graph $G$ and a given integer $k$ with $2\leq k\leq |V(G)|$ , the \emph{ $k$ -monochromatic vertex-index $mvx_k(G)$ } of $G$ is the maximum number of colors needed such that for each subset $S\subseteq V(G)$ of $k$ vertices, there exists a vertex-monochromatic $S$ -tree. We show that for a given a connected graph $G$ , and a positive integer $L$ with $L\leq |V(G)|$ , to decide whether $mvx_k(G)\geq L$ is NP-complete for each integer $k$ such that $2\leq k\leq |V(G)|$ . We also obtain some Nordhaus-Gaddum-type results for the $k$ -monochromatic vertex-index.

preprint2016arXiv

The $(k,\ell)$ -proper index of graphs

A tree $T$ in an edge-colored graph is called a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be an integer with $2\leq k \leq n$ . For $S\subseteq V(G)$ and $|S| \ge 2$ , an $S$ -tree is a tree containing the vertices of $S$ in $G$ . Suppose $\{T_1,T_2,\ldots,T_\ell\}$ is a set of $S$ -trees, they are called \emph{internally disjoint} if $E(T_i)\cap E(T_j)=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for $1\leq i\neq j\leq \ell$ . For a set $S$ of $k$ vertices of $G$ , the maximum number of internally disjoint $S$ -trees in $G$ is denoted by $κ(S)$ . The $κ$ -connectivity $κ_k(G)$ of $G$ is defined by $κ_k(G)=\min\{κ(S)\mid S$ is a $k$ -subset of $V(G)\}$ . For a connected graph $G$ of order $n$ and for two integers $k$ and $\ell$ with $2\le k\le n$ and $1\leq \ell \leq κ_k(G)$ , the \emph{ $(k,\ell)$ -proper index $px_{k,\ell}(G)$ } of $G$ is the minimum number of colors that are needed in an edge-coloring of $G$ such that for every $k$ -subset $S$ of $V(G)$ , there exist $\ell$ internally disjoint proper $S$ -trees connecting them. In this paper, we show that for every pair of positive integers $k$ and $\ell$ with $k \ge 3$ , there exists a positive integer $N_1=N_1(k,\ell)$ such that $px_{k,\ell}(K_n) = 2$ for every integer $n \ge N_1$ , and also there exists a positive integer $N_2=N_2(k,\ell)$ such that $px_{k,\ell}(K_{m,n}) = 2$ for every integer $n \ge N_2$ and $m=O(n^r) (r \ge 1)$ . In addition, we show that for every $p \ge c\sqrt[k]{\frac{\log_a n}{n}}$ ( $c \ge 5$ ), $px_{k,\ell}(G_{n,p})\le 2$ holds almost surely, where $G_{n,p}$ is the Erdös-Rényi random graph model.

preprint2016arXiv

The $k$ -proper index of complete bipartite and complete multipartite graphs

Let $G$ be a nontrivial connected graph of order $n$ with an edge-coloring $c:E(G)\rightarrow\{1,2,\dots,t\}$ , $t\in\mathbb{N}$ , where adjacent edges may be colored with the same color. A tree $T$ in $G$ is a \emph{proper tree} if no two adjacent edges of it are assigned the same color. Let $k$ be a fixed integer with $2\leq k\leq n$ . For a vertex subset $S\subseteq V(G)$ with $|S|\geq 2$ , a tree is called an \emph{ $S$ -tree} if it connects $S$ in $G$ . A \emph{ $k$ -proper coloring} of $G$ is an edge-coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$ , there exists a proper $S$ -tree $T$ in $G$ . The minimum number of colors that are needed in a $k$ -proper coloring of $G$ is defined as the \emph{ $k$ -proper index} of $G$ , denoted by $px_k(G)$ . In this paper, we determine the 3-proper index of all complete bipartite and complete multipartite graphs and partially determine the $k$ -proper index of them for $k\geq 4$ .

preprint2016arXiv

The $k$ -proper index of graphs

A tree $T$ in an edge-colored graph is a \emph{proper tree} if any two adjacent edges of $T$ are colored with different colors. Let $G$ be a graph of order $n$ and $k$ be a fixed integer with $2\leq k\leq n$ . For a vertex set $S\subseteq V(G)$ , a tree containing the vertices of $S$ in $G$ is called an \emph{ $S$ -tree}. An edge-coloring of $G$ is called a \emph{ $k$ -proper coloring} if for every set $S$ of $k$ vertices in $G$ , there exists a proper $S$ -tree in $G$ . The \emph{ $k$ -proper index} of a nontrivial connected graph $G$ , denoted by $px_k(G)$ , is the smallest number of colors needed in a $k$ -proper coloring of $G$ . In this paper, some simple observations about $px_k(G)$ for a nontrivial connected graph $G$ are stated. Meanwhile, the $k$ -proper indices of some special graphs are determined, and for every pair of positive integers $a$ , $b$ with $2\leq a\leq b$ , a connected graph $G$ with $px_k(G)=a$ and $rx_k(G)=b$ is constructed for each integer $k$ with $3\leq k\leq n$ . Also, the graphs with $k$ -proper index $n-1$ and $n-2$ are respectively characterized.

preprint2016arXiv

Total monochromatic connection of graphs

A graph is said to be {\it total-colored} if all the edges and the vertices of the graph are colored. A path in a total-colored graph is a {\it total monochromatic path} if all the edges and internal vertices on the path have the same color. A total-coloring of a graph is a {\it total monochromatically-connecting coloring} ({\it TMC-coloring}, for short) if any two vertices of the graph are connected by a total monochromatic path of the graph. For a connected graph $G$ , the {\it total monochromatic connection number}, denoted by $tmc(G)$ , is defined as the maximum number of colors used in a TMC-coloring of $G$ . These concepts are inspired by the concepts of monochromatic connection number $mc(G)$ , monochromatic vertex connection number $mvc(G)$ and total rainbow connection number $trc(G)$ of a connected graph $G$ . Let $l(T)$ denote the number of leaves of a tree $T$ , and let $l(G)=\max\{ l(T) |$ $T$ is a spanning tree of $G$ $\}$ for a connected graph $G$ . In this paper, we show that there are many graphs $G$ such that $tmc(G)=m-n+2+l(G)$ , and moreover, we prove that for almost all graphs $G$ , $tmc(G)=m-n+2+l(G)$ holds. Furthermore, we compare $tmc(G)$ with $mvc(G)$ and $mc(G)$ , respectively, and obtain that there exist graphs $G$ such that $tmc(G)$ is not less than $mvc(G)$ and vice versa, and that $tmc(G)=mc(G)+l(G)$ holds for almost all graphs. Finally, we prove that $tmc(G)\leq mc(G)+mvc(G)$ , and the equality holds if and only if $G$ is a complete graph.

preprint2015arXiv

$3$ -Regular mixed graphs with optimum Hermitian energy

Let $G$ be a simple undirected graph, and $G^ϕ$ be a mixed graph of $G$ with the generalized orientation $ϕ$ and Hermitian-adjacency matrix $H(G^ϕ)$ . Then $G$ is called the underlying graph of $G^ϕ$ . The Hermitian energy of the mixed graph $G^ϕ$ , denoted by $\mathcal{E}_H(G^ϕ)$ , is defined as the sum of all the singular values of $H(G^ϕ)$ . A $k$ -regular mixed graph on $n$ vertices having Hermitian energy $n\sqrt{k}$ is called a $k$ -regular optimum Hermitian energy mixed graph. In this paper, we first focus on the problem proposed by Liu and Li [J. Liu, X. Li, Hermitian-adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl. 466(2015), 182--207] of determining all the $3$ -regular connected optimum Hermitian energy mixed graphs. We then prove that optimum Hermitian energy oriented graphs with underlying graph hypercube are unique (up to switching equivalence).

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

A survey on the generalized connectivity of graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ was introduced by Hager before 1985. As its a natural counterpart, we introduced the concept of generalized edge-connectivity $λ_k(G)$ , recently. In this paper we summarize the known results on the generalized connectivity and generalized edge-connectivity. After an introductory section, the paper is then divided into nine sections: the generalized (edge-)connectivity of some graph classes, algorithms and computational complexity, sharp bounds of $κ_k(G)$ and $λ_k(G)$ , graphs with large generalized (edge-)connectivity, Nordhaus-Gaddum-type results, graph operations, extremal problems, and some results for random graphs and multigraphs. It also contains some conjectures and open problems for further studies.

preprint2015arXiv

A survey on the skew energy of oriented graphs

Let $G$ be a simple undirected graph with adjacency matrix $A(G)$ . The energy of $G$ is defined as the sum of absolute values of all eigenvalues of $A(G)$ , which was introduced by Gutman in 1970s. Since graph energy has important chemical applications, it causes great concern and has many generalizations. The skew energy and skew energy-like are the generalizations in oriented graphs. Let $G^σ$ be an oriented graph of $G$ with skew adjacency matrix $S(G^σ)$ . The skew energy of $G^σ$ , denoted by $\mathcal{E}_S(G^σ)$ , is defined as the sum of the norms of all eigenvalues of $S(G^σ)$ , which was introduced by Adiga, Balakrishnan and So in 2010. In this paper, we summarize main results on the skew energy of oriented graphs. Some open problems are proposed for further study. Besides, results on the skew energy-like: the skew Laplacian energy and skew Randić energy are also surveyed at the end.

preprint2015arXiv

Good upper bounds for the total rainbow connection of graphs

A total-colored graph is a graph $G$ such that both all edges and all vertices of $G$ are colored. A path in a total-colored graph $G$ is a total rainbow path if its edges and internal vertices have distinct colors. A total-colored graph $G$ is total-rainbow connected if any two vertices of $G$ are connected by a total rainbow path of $G$ . The total rainbow connection number of $G$ , denoted by $trc(G)$ , is defined as the smallest number of colors that are needed to make $G$ total-rainbow connected. These concepts were introduced by Liu et al. Notice that for a connected graph $G$ , $2diam(G)-1\leq trc(G)\leq 2n-3$ , where $diam(G)$ denotes the diameter of $G$ and $n$ is the order of $G$ . In this paper we show, for a connected graph $G$ of order $n$ with minimum degree $δ$ , that $trc(G)\leq6n/{(δ+1)}+28$ for $δ\geq\sqrt{n-2}-1$ and $n\geq 291$ , while $trc(G)\leq7n/{(δ+1)}+32$ for $16\leqδ\leq\sqrt{n-2}-2$ and $trc(G)\leq7n/{(δ+1)}+4C(δ)+12$ for $6\leqδ\leq15$ , where $C(δ)=e^{\frac{3\log(δ^3+2δ^2+3)-3(\log3-1)}{δ-3}}-2$ . This implies that when $δ$ is in linear with $n$ , then the total rainbow number $trc(G)$ is a constant. We also show that $trc(G)\leq 7n/4-3$ for $δ=3$ , $trc(G)\leq8n/5-13/5$ for $δ=4$ and $trc(G)\leq3n/2-3$ for $δ=5$ . Furthermore, an example shows that our bound can be seen tight up to additive factors when $δ\geq\sqrt{n-2}-1$ .

preprint2015arXiv

Graphs with large generalized (edge-)connectivity

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ , introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$ -edge-connectivity $λ_k(G)$ . In this paper, graphs of order $n$ such that $κ_k(G)=n-\frac{k}{2}-1$ and $λ_k(G)=n-\frac{k}{2}-1$ for even $k$ are characterized.

preprint2015arXiv

Hardness result for the total rainbow $k$ -connection of graphs

A path in a total-colored graph is called \emph{total rainbow} if its edges and internal vertices have distinct colors. For an $\ell$ -connected graph $G$ and an integer $k$ with $1\leq k \leq\ell$ , the \emph{total rainbow $k$ -connection number} of $G$ , denoted by $trc_k(G)$ , is the minimum number of colors used in a total coloring of $G$ to make $G$ \emph{total rainbow $k$ -connected}, that is, any two vertices of $G$ are connected by $k$ internally vertex-disjoint total rainbow paths. In this paper, we study the computational complexity of total rainbow $k$ -connection number of graphs. We show that it is NP-complete to decide whether $trc_k(G)=3$ .

preprint2015arXiv

Long rainbow path in properly edge-colored complete graphs

Let $G$ be an edge-colored graph. A rainbow (heterochromatic, or multicolored) path of $G$ is such a path in which no two edges have the same color. Let the color degree of a vertex $v$ be the number of different colors that are used on the edges incident to $v$ , and denote it to be $d^c(v)$ . It was shown that if $d^c(v)\geq k$ for every vertex $v$ of $G$ , then $G$ has a rainbow path of length at least $\min\{\lceil\frac{2k+1}{3}\rceil,k-1\}$ . In the present paper, we consider the properly edge-colored complete graph $K_n$ only and improve the lower bound of the length of the longest rainbow path by showing that if $n\geq 20$ , there must have a rainbow path of length no less than $\displaystyle \frac{3}{4}n-\frac{1}{4}\sqrt{\frac{n}{2}-\frac{39}{11}}-\frac{11}{16}$ .

preprint2015arXiv

On (strong) proper vertex-connection of graphs

A path in a vertex-colored graph is a {\it vertex-proper path} if any two internal adjacent vertices differ in color. A vertex-colored graph is {\it proper vertex $k$ -connected} if any two vertices of the graph are connected by $k$ disjoint vertex-proper paths of the graph. For a $k$ -connected graph $G$ , the {\it proper vertex $k$ -connection number} of $G$ , denoted by $pvc_{k}(G)$ , is defined as the smallest number of colors required to make $G$ proper vertex $k$ -connected. A vertex-colored graph is {\it strong proper vertex-connected}, if for any two vertices $u,v$ of the graph, there exists a vertex-proper $u$ - $v$ geodesic. For a connected graph $G$ , the {\it strong proper vertex-connection number} of $G$ , denoted by $spvc(G)$ , is the smallest number of colors required to make $G$ strong proper vertex-connected. These concepts are inspired by the concepts of rainbow vertex $k$ -connection number $rvc_k(G)$ , strong rainbow vertex-connection number $srvc(G)$ , and proper $k$ -connection number $pc_k(G)$ of a $k$ -connected graph $G$ . Firstly, we determine the value of $pvc(G)$ for general graphs and $pvc_k(G)$ for some specific graphs. We also compare the values of $pvc_k(G)$ and $pc_k(G)$ . Then, sharp bounds of $spvc(G)$ are given for a connected graph $G$ of order $n$ , that is, $0\leq spvc(G)\leq n-2$ . Moreover, we characterize the graphs of order $n$ such that $spvc(G)=n-2,n-3$ , respectively. Finally, we study the relationship among the three vertex-coloring parameters, namely, $spvc(G), \ srvc(G)$ and the chromatic number $χ(G)$ of a connected graph $G$ .

preprint2015arXiv

Proper connection number and 2-proper connection number of a graph

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored with one same color. An edge-colored graph is called $k$ -proper connected if any two vertices of the graph are connected by $k$ internally pairwise vertex-disjoint proper paths in the graph. The $k$ -proper connection number of a $k$ -connected graph $G$ , denoted by $pc_k(G)$ , is defined as the smallest number of colors that are needed in order to make $G$ $k$ -proper connected. For $k=1$ , we write $pc(G)$ other than $pc_1(G)$ , and call it the proper connection number of $G$ . In this paper, we present an upper bound for the proper connection number of a graph $G$ in terms of the minimum degree of $G$ , and give some sufficient conditions for a graph to have $2$ -proper connection number two. Also, we investigate the proper connection numbers of dense graphs.

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.

preprint2015arXiv

Proper connection number of random graphs

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored the same. For a connected graph $G$ , the proper connection number $pc(G)$ of $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 proper path in $G$ . In this paper, we show that almost all graphs have the proper connection number 2. More precisely, let $G(n,p)$ denote the Erdös-Rényi random graph model, in which each of the $\binom{n}{2}$ pairs of vertices appears as an edge with probability $p$ independent from other pairs. We prove that for sufficiently large $n$ , $pc(G(n,p))\le2$ if $p\ge\frac{\log n +α(n)}{n}$ , where $α(n)\rightarrow \infty$ .

preprint2015arXiv

Proper connection numbers of complementary graphs

A path $P$ in an edge-colored graph $G$ is called a proper path if no two adjacent edges of $P$ are colored the same, and $G$ is proper connected if every two vertices of $G$ are connected by a proper path in $G$ . The proper connection number of a connected graph $G$ , denoted by $pc(G)$ , is the minimum number of colors that are needed to make $G$ proper connected. In this paper, we investigate the proper connection number of the complement of graph $G$ according to some constraints of $G$ itself. Also, we characterize the graphs on $n$ vertices that have proper connection number $n-2$ . Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if $G$ and $\overline{G}$ are both connected, then $4\le pc(G)+pc(\overline{G})\le n$ , and the only graph attaining the upper bound is the tree with maximum degree $Δ=n-2$ .

preprint2015arXiv

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

A path in a vertex-colored graph is called a \emph{vertex-monochromatic path} if its internal vertices have the same color. A vertex-coloring of a graph is a \emph{monochromatic vertex-connection coloring} (\emph{MVC-coloring} for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph $G$ , the \emph{monochromatic vertex-connection number}, denoted by $mvc(G)$ , is defined to be the maximum number of colors used in an \emph{MVC-coloring} of $G$ . These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster. In this paper, we mainly investigate the Erdős-Gallai-type problems for the monochromatic vertex-connection number $mvc(G)$ and completely determine the exact value. Moreover, the Nordhaus-Gaddum-type inequality for $mvc(G)$ is also given.

preprint2015arXiv

Total proper connection of graphs

A graph is said to be {\it total-colored} if all the edges and the vertices of the graph is colored. A path in a total-colored graph is a {\it total proper path} if $(i)$ any two adjacent edges on the path differ in color, $(ii)$ any two internal adjacent vertices on the path differ in color, and $(iii)$ any internal vertex of the path differs in color from its incident edges on the path. A total-colored graph is called {\it total-proper connected} if any two vertices of the graph are connected by a total proper path of the graph. For a connected graph $G$ , the {\it total proper connection number} of $G$ , denoted by $tpc(G)$ , is defined as the smallest number of colors required to make $G$ total-proper connected. These concepts are inspired by the concepts of proper connection number $pc(G)$ , proper vertex connection number $pvc(G)$ and total rainbow connection number $trc(G)$ of a connected graph $G$ . In this paper, we first determine the value of the total proper connection number $tpc(G)$ for some special graphs $G$ . Secondly, we obtain that $tpc(G)\leq 4$ for any $2$ -connected graph $G$ and give examples to show that the upper bound $4$ is sharp. For general graphs, we also obtain an upper bound for $tpc(G)$ . Furthermore, we prove that $tpc(G)\leq \frac{3n}{δ+1}+1$ for a connected graph $G$ with order $n$ and minimum degree $δ$ . Finally, we compare $tpc(G)$ with $pvc(G)$ and $pc(G)$ , respectively, and obtain that $tpc(G)>pvc(G)$ for any nontrivial connected graph $G$ , and that $tpc(G)$ and $pc(G)$ can differ by $t$ for $0\leq t\leq 2$ .

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

An extension of Mantel's theorem to random 4-uniform hypergraphs

A sparse version of Mantel's Theorem is that, for sufficiently large $p$ , with high probability (w.h.p.), every maximum triangle-free subgraph of $G(n,p)$ is bipartite. DeMarco and Kahn proved this for $p>K \sqrt{\log n/n}$ for some constant $K$ , and apart from the value of the constant, this bound is the best possible. Denote by $T_3$ the 3-uniform hypergraph with vertex set $\{a,b,c,d,e\}$ and edge set $\{abc,ade,bde\}$ . Frankl and Füredi showed that the maximum 3-uniform hypergraph on $n$ vertices containing no copy of $T_3$ is tripartite for $n> 3000$ . For some integer $k$ , let $G^k(n,p)$ be the random $k$ -uniform hypergraph. Balogh et al. proved that for $p>K \log n/n$ for some constant $K$ , every maximum $T_3$ -free subhypergraph of $G^3(n,p)$ w.h.p. is tripartite and it does not hold when $p=0.1 \sqrt{\log n}/n$ . Denote by $T_4$ the 4-uniform hypergraph with vertex set $\{1,2,3,4,5,6,7\}$ and edge set $\{1234,1235,4567\}$ . Pikhurko proved that there is an $n_0$ such that for all $n\ge n_0$ , the maximum 4-uniform hypergraph on $n$ vertices containing no copy of $T_4$ is 4-partite. In this paper, we extend this type of extremal problem in random 4-uniform hypergraphs. We show that for some constant $K$ and $p>K \log n/n$ , w.h.p. every maximum $T_4$ -free subhypergraph of $G^4(n,p)$ is 4-partite.

preprint2014arXiv

Colorful monochromatic connectivity of random graphs

An edge-coloring of a connected graph $G$ is called a {\it monochromatic connection coloring} (MC-coloring, for short), introduced by Caro and Yuster, if there is a monochromatic path joining any two vertices of the graph $G$ . Let $mc(G)$ denote the maximum number of colors used in an MC-coloring of a graph $G$ . Note that an MC-coloring does not exist if $G$ is not connected, and in this case we simply let $mc(G)=0$ . We use $G(n,p)$ to denote the Erdös-Rényi random graph model, in which each of the $\binom{n}{2}$ pairs of vertices appears as an edge with probability $p$ independently from other pairs. For any function $f(n)$ satisfying $1\leq f(n)<\frac{1}{2}n(n-1)$ , we show that if $\ell n \log n\leq f(n)<\frac{1}{2}n(n-1)$ where $\ell\in \mathbb{R}^+$ , then $p=\frac{f(n)+n\log\log n}{n^2}$ is a sharp threshold function for the property $mc\left(G\left(n,p\right)\right)\ge f(n)$ ; if $f(n)=o(n\log n)$ , then $p=\frac{\log n}{n}$ is a sharp threshold function for the property $mc\left(G\left(n,p\right)\right)\ge f(n)$ .

preprint2014arXiv

Erdős-Gallai-type results for colorful monochromatic connectivity of a graph

A path in an edge-colored graph is called a \emph{monochromatic path} if all the edges on the path are colored the same. An edge-coloring of $G$ is a \emph{monochromatic connection coloring} (MC-coloring, for short) if there is a monochromatic path joining any two vertices in $G$ . The \emph{monochromatic connection number}, denoted by $mc(G)$ , is defined to be the maximum number of colors used in an MC-coloring of a graph $G$ . These concepts were introduced by Caro and Yuster, and they got some nice results. In this paper, we will study two kinds of Erdős-Gallai-type problems for $mc(G)$ , and completely solve them.

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

Lower bounds of the skew spectral radii and skew energy of oriented graphs

Let $G$ be a graph with maximum degree $Δ$ , and let $G^σ$ be an oriented graph of $G$ with skew adjacency matrix $S(G^σ)$ . The skew spectral radius $ρ_s(G^σ)$ of $G^σ$ is defined as the spectral radius of $S(G^σ)$ . The skew spectral radius has been studied, but only few results about its lower bound are known. This paper determines some lower bounds of the skew spectral radius, and then studies the oriented graphs whose skew spectral radii attain the lower bound $\sqrtΔ$ . Moreover, we apply the skew spectral radius to the skew energy of oriented graphs, which is defined as the sum of the norms of all the eigenvalues of $S(G^σ)$ , and denoted by $\mathcal{E}_s(G^σ)$ . As results, we obtain some lower bounds of the skew energy, which improve the known lower bound obtained by Adiga et al.

preprint2014arXiv

Note on the upper bound of the rainbow index of a graph

A path in an edge-colored graph $G$ , where adjacent edges may be colored the same, is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph $G$ , denoted by $rc(G)$ , is the minimum number of colors that are needed to color the edges of $G$ such that there exists a rainbow path connecting every two vertices of $G$ . Similarly, a tree in $G$ is a rainbow~tree if no two edges of it receive the same color. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow tree connecting $S$ for each $k$ -subset $S$ of $V(G)$ is called the $k$ -rainbow index of $G$ , denoted by $rx_k(G)$ , where $k$ is an integer such that $2\leq k\leq n$ . Chakraborty et al. got the following result: For every $ε> 0$ , a connected graph with minimum degree at least $εn$ has bounded rainbow connection, where the bound depends only on $ε$ . Krivelevich and Yuster proved that if $G$ has $n$ vertices and the minimum degree $δ(G)$ then $rc(G)<20n/δ(G)$ . This bound was later improved to $3n/(δ(G)+1)+3$ by Chandran et al. Since $rc(G)=rx_2(G)$ , a natural problem arises: for a general $k$ determining the true behavior of $rx_k(G)$ as a function of the minimum degree $δ(G)$ . In this paper, we give upper bounds of $rx_k(G)$ in terms of the minimum degree $δ(G)$ in different ways, namely, via Szemerédi's Regularity Lemma, connected $2$ -step dominating sets, connected $(k-1)$ -dominating sets and $k$ -dominating sets of $G$ .

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.

preprint2014arXiv

On a Problem of Harary and Schwenk on Graphs with Distinct Eigenvalues

Harary and Schwenk posed the problem forty years ago: Which graphs have distinct adjacency eigenvalues? In this paper, we obtain a necessary and sufficient condition for an Hermitian matrix with simple spectral radius and distinct eigenvalues. As its application, we give an algebraic characterization to the Harary-Schwenk's problem. As an extension of their problem, we also obtain a necessary and sufficient condition for a positive semidefinite matrix with simple least eigenvalue and distinct eigenvalues, which can provide an algebraic characterization to their problem with respect to the (normalized) Laplacian matrix.

preprint2014arXiv

On graphs with maximum Harary spectral radius

Let $G$ be a simple graph with vertex set $V(G) = \{v_1 ,v_2 ,\cdots ,v_n\}$ . The Harary matrix $RD(G)$ of $G$ , which is initially called the reciprocal distance matrix, is an $n \times n$ matrix whose $(i,j)$ -entry is equal to $\frac{1}{d_{ij}}$ if $i\not=j$ and $0$ otherwise, where $d_{ij}$ is the distance of $v_i$ and $v_j$ in $G$ . In this paper, we characterize graphs with maximum spectral radius of Harary matrix in three classes of simple connected graphs with $n$ vertices: graphs with fixed matching number, bipartite graphs with fixed matching number, and graphs with given number of cut edges, respectively.

preprint2014arXiv

On maximum Estrada indices of bipartite graphs with some given parameters

The Estrada index of a graph $G$ is defined as $EE(G)=\sum_{i=1}^ne^{λ_i}$ , where $λ_1,$ $λ_2,\ldots, λ_n$ are the eigenvalues of the adjacency matrix of $G$ . In this paper, we characterize the unique bipartite graph with maximum Estrada index among bipartite graphs with given matching number and given vertex-connectivity, edge-connectivity, respectively.

preprint2014arXiv

Polynomial reconstruction of the matching polynomial

The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex-deleted subgraphs of the same graph. This note discusses the polynomial reconstructibility of the matching polynomial. We collect previous results, prove it for graphs with pendant edges and disprove it for some graphs.

preprint2014arXiv

Randić energy and Randić eigenvalues

Let $G$ be a graph of order $n$ , and $d_i$ the degree of a vertex $v_i$ of $G$ . The Randić matrix ${\bf R}=(r_{ij})$ of $G$ is defined by $r_{ij} = 1 / \sqrt{d_jd_j}$ if the vertices $v_i$ and $v_j$ are adjacent in $G$ and $r_{ij}=0$ otherwise. The normalized signless Laplacian matrix $\mathcal{Q}$ is defined as $\mathcal{Q} =I+\bf{R}$ , where $I$ is the identity matrix. The Randić energy is the sum of absolute values of the eigenvalues of $\bf{R}$ . In this paper, we find a relation between the normalized signless Laplacian eigenvalues of $G$ and the Randić energy of its subdivided graph $S(G)$ . We also give a necessary and sufficient condition for a graph to have exactly $k$ and distinct Randić eigenvalues.

preprint2014arXiv

Randić Incidence Energy of Graphs

Let $G$ be a simple graph with vertex set $V(G) = \{v_1, v_2,\ldots, v_n\}$ and edge set $E(G) = \{e_1, e_2,\ldots, e_m\}$ . Similar to the Randić matrix, here we introduce the Randić incidence matrix of a graph $G$ , denoted by $I_R(G)$ , which is defined as the $n\times m$ matrix whose $(i, j)$ -entry is $(d_i)^{-\frac{1}{2}}$ if $v_i$ is incident to $e_j$ and $0$ otherwise. Naturally, the Randić incidence energy $I_RE$ of $G$ is the sum of the singular values of $I_R(G)$ . We establish lower and upper bounds for the Randić incidence energy. Graphs for which these bounds are best possible are characterized. Moreover, we investigate the relation between the Randić incidence energy of a graph and that of its subgraphs. Also we give a sharp upper bound for the Randić incidence energy of a bipartite graph and determine the trees with the maximum Randić incidence energy among all $n$ -vertex trees. As a result, some results are very different from those for incidence energy.

preprint2014arXiv

Skew Randić Matrix and Skew Randić Energy

Let $G$ be a simple graph with an orientation $σ$ , which assigns to each edge a direction so that $G^σ$ becomes a directed graph. $G$ is said to be the underlying graph of the directed graph $G^σ$ . In this paper, we define a weighted skew adjacency matrix with Randć weight, the skew Randić matrix ${\bf R_S}(G^σ)$ , of $G^σ$ as the real skew symmetric matrix $[(r_s)_{ij}]$ where $(r_s)_{ij} = (d_id_j)^{-\frac{1}{2}}$ and $(r_s)_{ji} = -(d_id_j)^{-\frac{1}{2}}$ if $v_i \rightarrow v_j$ is an arc of $G^σ$ , otherwise $(r_s)_{ij} = (r_s)_{ji} = 0$ . We derive some properties of the skew Randić energy of an oriented graph. Most properties are similar to those for the skew energy of oriented graphs. But, surprisingly, the extremal oriented graphs with maximum or minimum skew Randić energy are completely different.

preprint2014arXiv

Solution to a conjecture on the maximum skew-spectral radius of odd-cycle graphs

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Cavers et al. Skew-adjacency matrices of graphs, Linear Algebra Appl. 436(2012), 4512--1829] showed that the spectral radius of $G^σ$ is the same for every orientation $σ$ of $G$ , and equals the maximum matching root of $G$ . They proposed a conjecture that the graphs which attain the maximum skew spectral radius among the odd-cycle graphs $G$ of order $n$ are isomorphic to the odd-cycle graph with one vertex degree $n-1$ and size $m=\lfloor 3(n-1)/2\rfloor$ . This paper, by using the Kelmans transformation, gives a proof of the conjecture. Moreover, sharp upper bounds of the maximum matching roots of the odd-cycle graphs with given order $n$ and size $m$ are given and extremal graphs are characterized.

preprint2014arXiv

The 3-rainbow index and connected dominating sets

A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of $G$ is called 3-rainbow if for any three vertices in $G$ , there exists a rainbow tree connecting them. The 3-rainbow index $rx_3(G)$ of $G$ is defined as the minimum number of colors that are needed in a 3-rainbow coloring of $G$ . This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected three-way dominating sets and 3-dominating sets. We shown that for every connected graph $G$ on $n$ vertices with minimum degree at least $δ$ ( $3\leqδ\leq5$ ), $rx_{3}(G)\leq \frac{3n}{δ+1}+4$ , and the bound is tight up to an additive constant; whereas for every connected graph $G$ on $n$ vertices with minimum degree at least $δ$ ( $δ\geq3$ ), we get that $rx_{3}(G)\leq n\frac{ln(δ+1)}{δ+1}(1+o_δ(1))+5$ . In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.

preprint2014arXiv

The generalized 3-edge-connectivity of lexicographic product graphs

The generalized $k$ -edge-connectivity $λ_k(G)$ of a graph $G$ is a generalization of the concept of edge-connectivity. The lexicographic product of two graphs $G$ and $H$ , denoted by $G\circ H$ , is an important graph product. In this paper, we mainly study the generalized 3-edge-connectivity of $G \circ H$ , and get upper and lower bounds of $λ_3(G \circ H)$ . Moreover, all bounds are sharp.

preprint2014arXiv

The matching energy of random graphs

The matching energy of a graph was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial of the graph. For the random graph $G_{n,p}$ of order $n$ with fixed probability $p\in (0,1)$ , Gutman and Wagner [I. Gutman, S. Wagner, The matching energy of a graph, Discrete Appl. Math. 160(2012), 2177--2187] proposed a conjecture that the matching energy of $G_{n,p}$ converges to $\frac{8\sqrt{p}}{3π}n^{\frac{3}{2}}$ almost surely. In this paper, using analysis method, we prove that the conjecture is true.

preprint2014arXiv

The skew-rank of oriented graphs

An oriented graph $G^σ$ is a digraph without loops and multiple arcs, where $G$ is called the underlying graph of $G^σ$ . Let $S(G^σ)$ denote the skew-adjacency matrix of $G^σ$ . The rank of the skew-adjacency matrix of $G^σ$ is called the {\it skew-rank} of $G^σ$ , denoted by $sr(G^σ)$ . The skew-adjacency matrix of an oriented graph is skew symmetric and the skew-rank is even. In this paper we consider the skew-rank of simple oriented graphs. Firstly we give some preliminary results about the skew-rank. Secondly we characterize the oriented graphs with skew-rank 2 and characterize the oriented graphs with pendant vertices which attain the skew-rank 4. As a consequence, we list the oriented unicyclic graphs, the oriented bicyclic graphs with pendant vertices which attain the skew-rank 4. Moreover, we determine the skew-rank of oriented unicyclic graphs of order $n$ with girth $k$ in terms of matching number. We investigate the minimum value of the skew-rank among oriented unicyclic graphs of order $n$ with girth $k$ and characterize oriented unicyclic graphs attaining the minimum value. In addition, we consider oriented unicyclic graphs whose skew-adjacency matrices are nonsingular.

Xueliang Li

Research overview

Is this your work?

158 publications

Asymptotic values of four Laplacian-type energies for matrices with degree-distance-based entries of random graphs

Bounds for the rainbow disconnection number of graphs

Complexity results for two kinds of colored disconnections of graphs

Further results on the rainbow vertex-disconnection of graphs

Graph colorings under global structural conditions

Group Connectivity under 333-Edge-Connectivity

Hardness results for three kinds of colored connections of graphs

Monochromatic disconnection: Erdős-Gallai-type problems and product graphs

Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles

Rainbow monochromatic kkk-edge-connection colorings of graphs

Strong rainbow disconnection in graphs

The asymptotic value of energy for matrices with degree-distance-based entries of random graphs

The asymptotic value of graph energy for random graphs with degree-based weights

The rainbow vertex-disconnection in graphs

Upper bounds for the MDMDMD-numbers and characterization of extremal graphs

3-Rainbow index and forbidden subgraphs

A Source-level Energy Optimization Framework for Mobile Applications

An Energy-Aware Programming Approach for Mobile Application Development Guided by a Fine-Grained Energy Model

Degree sum conditions for graphs to have proper connection number 2

Derivatives and real roots of graph polynomials

Distance proper connection of graphs

Distance proper connection of graphs and their complements

ENTRA: Whole-Systems Energy Transparency

Erdős-Gallai-type results for total monochromatic connection of graphs

Fine-Grained Energy Modeling for the Source Code of a Mobile Application

More on total monochromatic connection of graphs

Nordhaus-Gaddum-type theorem for total proper connection number of graphs

On two conjectures about the proper connection number of graphs

Rainbow vertex-connection and forbidden subgraphs

Solution to a conjecture on the proper connection number of graphs

Solutions for two conjectures on kaleidoscopic edge-colorings

Some upper bounds for the 333-proper index of graphs

The (vertex-)monochromatic index of a graph

The (k,ℓ)(k,\ell)(k,ℓ)-proper index of graphs

The kkk-proper index of complete bipartite and complete multipartite graphs

The kkk-proper index of graphs

Total monochromatic connection of graphs

333-Regular mixed graphs with optimum Hermitian energy

A survey of recent results in (generalized) graph entropies

A survey on the generalized connectivity of graphs

A survey on the skew energy of oriented graphs

Good upper bounds for the total rainbow connection of graphs

Graphs with large generalized (edge-)connectivity

Hardness result for the total rainbow kkk-connection of graphs

Long rainbow path in properly edge-colored complete graphs

On (strong) proper vertex-connection of graphs

Proper connection number and 2-proper connection number of a graph

Proper connection number and connected dominating sets

Proper connection number of random graphs

Proper connection numbers of complementary graphs

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

Total proper connection of graphs

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

An extension of Mantel's theorem to random 4-uniform hypergraphs

Colorful monochromatic connectivity of random graphs

Erdős-Gallai-type results for colorful monochromatic connectivity of a graph

Formally self-dual linear binary codes from circulant graphs

Lower bounds of the skew spectral radii and skew energy of oriented graphs

Note on the upper bound of the rainbow index of a graph

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

On a conjecture about tricyclic graphs with maximal energy

On a Problem of Harary and Schwenk on Graphs with Distinct Eigenvalues

On graphs with maximum Harary spectral radius

On maximum Estrada indices of bipartite graphs with some given parameters

Polynomial reconstruction of the matching polynomial

Randić energy and Randić eigenvalues

Randić Incidence Energy of Graphs

Skew Randić Matrix and Skew Randić Energy

Solution to a conjecture on the maximum skew-spectral radius of odd-cycle graphs

The 3-rainbow index and connected dominating sets

The generalized 3-edge-connectivity of lexicographic product graphs

The matching energy of random graphs

The skew-rank of oriented graphs

A Turán-type problem on degree sequence

A Turán-type problem on distance two

Characterize graphs with rainbow connection number m−2m-2m−2 and m−3m-3m−3

Group Connectivity under $3$ -Edge-Connectivity

Rainbow monochromatic $k$ -edge-connection colorings of graphs

Upper bounds for the $MD$ -numbers and characterization of extremal graphs

Some upper bounds for the $3$ -proper index of graphs

The $(k,\ell)$ -proper index of graphs

The $k$ -proper index of complete bipartite and complete multipartite graphs

The $k$ -proper index of graphs

$3$ -Regular mixed graphs with optimum Hermitian energy

Hardness result for the total rainbow $k$ -connection of graphs

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

Characterize graphs with rainbow connection number $m-2$ and $m-3$

Degree powers in $C_5$ -free graphs

Graphs with $4$ -rainbow index $3$ and $n-1$

Graphs with 3-rainbow index $n-1$ and $n-2$

On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

On extremal graphs with exactly one Steiner tree connecting any $k$ vertices

The $(k,\ell)$ -rainbow index for complete bipartite and multipartite graphs

The $(k,\ell)$ -rainbow index of random graphs

Note on minimally $k$ -rainbow connected graphs

Rainbow $k$ -connectivity of random bipartite graphs

Solutions to conjectures on the $(k,\ell)$ -rainbow index of complete graphs

The minimal size of a graph with generalized connectivity $κ_3 = 2$

Two rainbow connection numbers and the parameter $σ_k(G)$

Upper bounds involving parameter $σ_2$ for the rainbow connection

Note on the Rainbow $k$ -Connectivity of Regular Complete Bipartite Graphs