Markov Chains Based on Random Generalized 1-Flipper Operations for Connected Regular Multi-digraphs

The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.

Signed total domination in nearly regular graphs

A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.

Search algorithm on strongly regular graphs based on scattering quantum walks

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

A Note on Strongly Regular Self-complementary Graphs

Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.

REGULAR k-COVERED GRAPHS

A graph G is k-covered if each edge of G belongs to a k-factor of G. We determine some valuee of k for which every r-regular graph with edge-connectivity λ is k-covered.

Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs

A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.

The Zero-divisor Graphs of Abelian Regular Rings

We introduce the zero-divisor graph for an abelian regular ring and show that if R,S are abelian regular, then (K0(R),[R])≌(K0(S),[S]) if and only if they have isomorphic reduced zero-divisor graphs. It is shown that the maximal right quotient ring of a potent semiprimitive normal ring is abelian regular, moreover, the zero-divisor graph of such a ring is studied.

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.

Two-level Bregmanized method for image interpolation with graph regularized sparse coding

A two-level Bregmanized method with graph regularized sparse coding （TBGSC） is presented for image interpolation. The outer-level Bregman iterative procedure enforces the observation data constraints, while the inner-level Bregmanized method devotes to dictionary updating and sparse represention of small overlapping image patches. The introduced constraint of graph regularized sparse coding can capture local image features effectively, and consequently enables accurate reconstruction from highly undersampled partial data. Furthermore, modified sparse coding and simple dictionary updating applied in the inner minimization make the proposed algorithm converge within a relatively small number of iterations. Experimental results demonstrate that the proposed algorithm can effectively reconstruct images and it outperforms the current state-of-the-art approaches in terms of visual comparisons and quantitative measures.

Graph Regularized L_p Smooth Non-negative Matrix Factorization for Data Representation

This paper proposes a Graph regularized Lpsmooth non-negative matrix factorization(GSNMF) method by incorporating graph regularization and L_p smoothing constraint, which considers the intrinsic geometric information of a data set and produces smooth and stable solutions. The main contributions are as follows: first, graph regularization is added into NMF to discover the hidden semantics and simultaneously respect the intrinsic geometric structure information of a data set. Second,the Lpsmoothing constraint is incorporated into NMF to combine the merits of isotropic(L_2-norm) and anisotropic(L_1-norm)diffusion smoothing, and produces a smooth and more accurate solution to the optimization problem. Finally, the update rules and proof of convergence of GSNMF are given. Experiments on several data sets show that the proposed method outperforms related state-of-the-art methods.

ON GRAPHS WITH THREE DISTINCT LAPLACIAN EIGENVALUES

In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.

Graph Regularized Sparse Coding Method for Highly Undersampled MRI Reconstruction

The imaging speed is a bottleneck for magnetic resonance imaging( MRI) since it appears. To alleviate this difficulty,a novel graph regularized sparse coding method for highly undersampled MRI reconstruction( GSCMRI) was proposed. The graph regularized sparse coding showed the potential in maintaining the geometrical information of the data. In this study, it was incorporated with two-level Bregman iterative procedure that updated the data term in outer-level and learned dictionary in innerlevel. Moreover,the graph regularized sparse coding and simple dictionary updating stages derived by the inner minimization made the proposed algorithm converge in few iterations, meanwhile achieving superior reconstruction performance. Extensive experimental results have demonstrated GSCMRI can consistently recover both real-valued MR images and complex-valued MR data efficiently,and outperform the current state-of-the-art approaches in terms of higher PSNR and lower HFEN values.

The Cordiality on the Union of 3-regular Connected Graph and Cycle

Diab proved the following graphs are Cordial;Pm K1,n if and only if(m,n) =(1,2);Cm K1,n;Pm Kn;Cm Kn for all m and n except m ≡ 2(mod 4).In this paper,we proved the Cordiality on the union of 3-regular connected graph K3 and cycle Cm.First we have the Lemma 2,if uv ∈ E(G),G is Cordial,we add 4 vertices x,y,z,w in sequence to the edge uv,obtain a new graph denoted by G*,then G* is still Cordial,by this lemma,we consider four cases on the union of 3-regular connected graph R3,and for every case we distinguish four subcases on the cycle Cm.

Extracting Sub-Networks from Brain Functional Network Using Graph Regularized Nonnegative Matrix Factorization

Currently,functional connectomes constructed from neuroimaging data have emerged as a powerful tool in identifying brain disorders.If one brain disease just manifests as some cognitive dysfunction,it means that the disease may affect some local connectivity in the brain functional network.That is,there are functional abnormalities in the sub-network.Therefore,it is crucial to accurately identify them in pathological diagnosis.To solve these problems,we proposed a sub-network extraction method based on graph regularization nonnegative matrix factorization(GNMF).The dynamic functional networks of normal subjects and early mild cognitive impairment(eMCI)subjects were vectorized and the functional connection vectors(FCV)were assembled to aggregation matrices.Then GNMF was applied to factorize the aggregation matrix to get the base matrix,in which the column vectors were restored to a common sub-network and a distinctive sub-network,and visualization and statistical analysis were conducted on the two sub-networks,respectively.Experimental results demonstrated that,compared with other matrix factorization methods,the proposed method can more obviously reflect the similarity between the common subnetwork of eMCI subjects and normal subjects,as well as the difference between the distinctive sub-network of eMCI subjects and normal subjects,Therefore,the high-dimensional features in brain functional networks can be best represented locally in the lowdimensional space,which provides a new idea for studying brain functional connectomes.

THE REGULARITY OF RANDOM GRAPH DIRECTED SELF-SIMILAR SETS

A set in Rd is called regular if its Hausdorff dimension coincides with its upper box counting dimension. It is proved that a random graph-directed self-similar set is regular a.e..

A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.

Zeta Functions of the Complement and xyz-Transformations of a Regular Graph

Let Z(λ,G)denote the zeta function of a graph G.In this paper the complement G^Cand the G^(xyz)-transformation G^(xyz)of an r-regular graph G with n vertices and m edges for x,y,z∈{0,1,+,-},are considerd.The relationship between Z(λ,G)and Z(λ,G^C)is obtained.For all x,y,z∈{0,1,+,-},the explicit formulas for the reciprocal of Z(λ,G^(xyz))in terms of r,m,n and the characteristic polynomial of G are obtained.Due to limited space,only the expressions for G^(xyz)with z=0,and xyz∈{0++,+++,1+-}are presented here.

Binomial Hadamard Series and Inequalities over the Spectra of a Strongly Regular Graph

Let G be a primitive strongly regular graph of order n and A is adjacency matrix. In this paper we first associate to A a real 3-dimensional Euclidean Jordan algebra? with rank three spanned by In and the natural powers of A that is a subalgebra of the Euclidean Jordan algebra of symmetric matrix of order n. Next we consider a basis? that is a Jordan frame of . Finally, by an algebraic asymptotic analysis of the second spectral decomposition of some Hadamard series associated to A we establish some inequalities over the spectra and over the parameters of a strongly regular graph.

Total Domination number of Generalized Petersen Graphs

Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.