Proximity and average eccentricity of a graph

Let $G=(V,E)$ be a connected graph on n vertices. The proximity $\pi (G)$ of G is the minimum average distance from a vertex of G to all others. The eccentricity $e(v)$ of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity $\mathit{ecc}(G)$ of the graph G is $\frac{1}{n}{\sum }_{v\in V(G)}e(v)$. Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on $n?3$ vertices, $\mathit{ecc}(G)?\pi (G)?\mathit{ecc}(P_n)?\pi (P_n)$, with equality if and only if $G?P_n$. In this paper, we show that this conjecture is true.     

Hardness of approximating the Shortest Vector Problem in high ℓp norms

We present a new hardness of approximation result for the Shortest Vector Problem in ${\ell }_p$ norm (denoted by ${\mathrm{SVP}}_p$). Assuming NP $⊈$ ZPP, we show that for every $\epsilon >0$, there is a constant $p(\epsilon )$ such that for all integers $p⩾p(\epsilon )$, the problem ${\mathrm{SVP}}_p$ has no polynomial time approximation algorithm with approximation ratio $p^{1-\epsilon }$.     

Longest paths and cycles in faulty star graphs

In this paper, we investigate the star graph $S_n$ with faulty vertices and/or edges from the graph theoretic point of view. We show that between every pair of vertices with different colors in a bicoloring of $S_n$, $n⩾4$, there is a fault-free path of length at least $n!-2f_v-1$, and there is a path of length at least $n!-2f_v-2$ joining a pair of vertices with the same color, when the number of faulty elements is $n-3$ or less. Here, $f_v$ is the number of faulty vertices. $S_n$, $n⩾4$, with at most $n-2$ faulty elements has a fault-free cycle of length at least $n!-2f_v$ unless the number of faulty elements are $n-2$ and all the faulty elements are edges incident to a common vertex. It is also shown that $S_n$, $n⩾4$, is strongly hamiltonian-laceable if the number of faulty elements is $n-3$ or less and the number of faulty vertices is one or less.     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.     

Finite iterative Hermitian R-conjugate solutions of the generalized coupled Sylvester-conjugate matrix equations

In this paper, an iterative algorithm for solving a generalized coupled Sylvester-conjugate matrix equations over Hermitian $R$-conjugate matrices given by $A_{1}V{B}_1+C_{1}W{D}_1=E_1\overline{V}{F}_1+G_1$ and $A_{2}V{B}_2+C_{2}W{D}_2=E_2\overline{V}{F}_2+G_2$ is presented. When these two matrix equations are consistent, the convergence theorem shows that a solution can be obtained within finite iterative steps in the absence of round-off error for any initial arbitrary Hermitian $R$-conjugate solution matrices $V_1$, $W_1$. Some lemmas and theorems are stated and proved where the iterative solutions are obtained. A numerical example is given to demonstrate the behavior of the proposed method and to support the theoretical results.     

Relations between matrix sets generated from linear matrix expressions and their applications

Let $A+BXC$ and $A+BX+YC$ be two linear matrix expressions, and denote by $\{A+BXC\}$ and $\{A+BX+YC\}$ the collections of the two matrix expressions when $X$ and $Y$ run over the corresponding matrix spaces. In this paper, we study relationships between the two matrix sets $\{A_1+B_1{X}_1{C}_1\}$ and $\{A_2+B_2{X}_2{C}_2\}$, as well as the two sets $\{A_1+B_1{X}_1+Y_1{C}_1\}$ and $\{A_2+B_2{X}_2+Y_2{C}_2\}$, by using some rank formulas for matrices. In particular, we give necessary and sufficient conditions for the two matrix set inclusions $\{A_1+B_1{X}_1{C}_1\}?\{A_2+B_2{X}_2{C}_2\}$ and $\{A_1+B_1{X}_1+Y_1{C}_1\}?\{A_2+B_2{X}_2+Y_2{C}_2\}$ to hold. We also use the results obtained to characterize relations of solutions of some linear matrix equations.