The Cycle Discrepancy of Three-Regular Graphs

Let G = (V, E) be an undirected graph and C(G){{\mathcal C}(G)} denote the set of all cycles in G. We introduce a graph invariant cycle discrepancy, which we define as

A Note on Heterochromatic C 4 in Edge-Colored Triangle-Free Graphs

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥?9 and ${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$ for each vertex v of G, G has a heterochromatic C ₄.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

On super vertex-graceful unicyclic graphs

A graph G with p vertices and q edges, vertex set V(G) and edge set E(G), is said to be super vertex-graceful (in short SVG), if there exists a function pair (f, f ⁺) where f is a bijection from V(G) onto P, f ⁺ is a bijection from E(G) onto Q, f ⁺((u, v)) = f(u) + f(v) for any (u, v) ∈ E(G),

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

Entropy,Periodicity, and Graphs with Zero Euler Characteristic

Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G.     

General Construction of Non-Dense Disjoint Iteration Groups on the Circle

Let be a disjoint iteration group on the unit circle , that is a family of homeomorphisms such that F ^v1 ○ F ^v2 = F ^v1+v2 for v ₁, v ₂ ∈ V and each F ^v either is the identity mapping or has no fixed point ((V, +) is a 2-divisible nontrivial Abelian group). Denote by the set of all cluster points of {F ^v (z), v ∈ V} for . In this paper we give a general construction of disjoint iteration groups for which .     

Star number and star arboricity of a complete multigraph

Let G be a multigraph. The star number s(G) of G is the minimum number of stars needed to decompose the edges of G. The star arboricity sa(G) of G is the minimum number of star forests needed to decompose the edges of G. As usual λK _n denote the λ-fold complete graph on n vertices (i.e., the multigraph on n vertices such that there are λ edges between every pair of vertices). In this paper, we prove that for n ⩾ 2

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      10. Matchings and walks in graphs      C. D. Godsil 《Journal of Graph Theory》1981,5(3):285-297 The matching polynomial α(G, x) of a graph G is a form of the generating function for the number of sets of k independent edges of G. in this paper we show that if G is a graph with vertex v then there is a tree T with vertex w such that \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document} This result has a number of consequences. Here we use it to prove that α(G\v, 1/x)/xα(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).      11. Degree Bounded Spanning Trees      Jun Fujisawa  Hajime Matsumura  Tomoki Yamashita 《Graphs and Combinatorics》2010,26(5):695-720 In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .      12. The Existence of BIB Designs      Yanxun Chang 《数学学报(英文版)》2000,16(1):103-112 Abstract Given any positive integers k≥ 3 and λ, let c(k, λ) denote the smallest integer such that v∈B(k, λ) for every integer v≥c(k, λ) that satisfies the congruences λv(v− 1) ≡ 0(mod k(k− 1)) and λ(v− 1) ≡ 0(mod k− 1). In this article we make an improvement on the bound of c(k, λ) provided by Chang in [4] and prove that . In particular, . Supported by NSFC Grant No. 19701002 and Huo Yingdong Foundation      13. Lifts, Discrepancy and Nearly Optimal Spectral Gap*      Yonatan Bilu  Nathan Linial 《Combinatorica》2006,26(5):495-519 We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l1 norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}n with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.      14. <Emphasis Type="Italic">c</Emphasis>*-Supplemented subgroups and <Emphasis Type="Italic">p</Emphasis>-nilpotency of finite groups      H. Wei  Y. Wang 《Ukrainian Mathematical Journal》2007,59(8):1121-1129 A subgroup H of a finite group G is said to be c*-supplemented in G if there exists a subgroup K such that G = HK and H ⋂ K is permutable in G. It is proved that a finite group G that is S 4-free is p-nilpotent if N G (P) is p-nilpotent and, for all x ∈ G\N G (P), every minimal subgroup of is c*-supplemented in P and (if p = 2) one of the following conditions is satisfied: (a) every cyclic subgroup of of order 4 is c*-supplemented in P, (b) , (c) P is quaternion-free, where P a Sylow p-subgroup of G and is the p-nilpotent residual of G. This extends and improves some known results. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1011–1019, August, 2007.      15. Distance-2-Matchings of Random Graphs      C.?M.?ReidysEmail author 《Annals of Combinatorics》2004,8(1):93-101 In this paper we study the maximal size of a distance-2-matching in a random graph G n;M , i.e., the probability space consisting of subgraphs of the complete graph over n vertices, K n , having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M 2, is a set of Y-edges with the property that for any two elements every pair of their 4 incident vertices has Y-distance 2. Let M2(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M2(Y) and a sharp concentration result for the random variable AMS Subject Classification: 05C80, 05C70.      16. The upper traceable number of a graph      Futaba Okamoto  Ping Zhang  Varaporn Saenpholphat 《Czechoslovak Mathematical Journal》2008,58(1):271-287 For a nontrivial connected graph G of order n and a linear ordering s: v 1, v 2, …, v n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t +(G) of G is t +(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t +(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.      17. Exact asymptotic behaviour of the codimensions of some P.I. algebras      Vesselin Drensky  Amitai Regev 《Israel Journal of Mathematics》1996,96(1):231-242 Letc n (A) denote the codimensions of a P.I. algebraA, and assumec n (A) has a polynomial growth: . Then, necessarily,q∈ℚ [D3]. If 1∈A, we show that , wheree=2.71…. In the non-unitary case, for any 0<q∈ℚ, we constructA, with a suitablek, such that . In memory of S. A. Amitsur, our teacher and friend Partially supported by Grant MM404/94 of Ministry of Education and Science, Bulgaria and by a Bulgarian-American Grant of NSF. Partially supported by NSF grant DMS-9101488.      18. Roman domination subdivision number of graphs      M. Atapour  S. M. Sheikholeslami  Abdollah Khodkar 《Aequationes Mathematicae》2009,78(3):237-245 A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?v ? V f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sdgR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.      19. Characterization of Amalgamated Free Blocks of a Graph von Neumann Algebra      Ilwoo Cho 《Complex Analysis and Operator Theory》2007,1(3):367-398 We identify two noncommutative structures naturally associated with countable directed graphs. They are formulated in the language of operators on Hilbert spaces. If G is a countable directed graphs with its vertex set V(G) and its edge set E(G), then we associate partial isometries to the edges in E(G) and projections to the vertices in V(G). We construct a corresponding von Neumann algebra as a groupoid crossed product algebra of an arbitrary fixed von Neumann algebra M and the graph groupoid induced by G, via a graph-representation (or a groupoid action) α. Graph groupoids are well-determined (categorial) groupoids. The graph groupoid of G has its binary operation, called admissibility. This has concrete local parts , for all e ∈ E(G). We characterize of , induced by the local parts of , for all e ∈ E(G). We then characterize all amalgamated free blocks of . They are chracterized by well-known von Neumann algebras: the classical group crossed product algebras , and certain subalgebras (M) of operator-valued matricial algebra . This shows that graph von Neumann algebras identify the key properties of graph groupoids. Received: December 20, 2006. Revised: March 07, 2007. Accepted: March 13, 2007.      20. Lower bounds on signed edge total domination numbers in graphs      H. Karami  S. M. Sheikholeslami  Abdollah Khodkar 《Czechoslovak Mathematical Journal》2008,58(3):595-603 The open neighborhood N G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ st ′(G). Obviously, γ st ′(G) is defined only for graphs G which have no connected components isomorphic to K 2. In this paper we present some lower bounds for γ st ′(G). In particular, we prove that γ st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.

Matchings and walks in graphs

The matching polynomial α(G, x) of a graph G is a form of the generating function for the number of sets of k independent edges of G. in this paper we show that if G is a graph with vertex v then there is a tree T with vertex w such that \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document} This result has a number of consequences. Here we use it to prove that α(G\v, 1/x)/xα(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

The Existence of BIB Designs

Abstract Given any positive integers k≥ 3 and λ, let c(k, λ) denote the smallest integer such that v∈B(k, λ) for every integer v≥c(k, λ) that satisfies the congruences λv(v− 1) ≡ 0(mod k(k− 1)) and λ(v− 1) ≡ 0(mod k− 1). In this article we make an improvement on the bound of c(k, λ) provided by Chang in [4] and prove that . In particular, . Supported by NSFC Grant No. 19701002 and Huo Yingdong Foundation     

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

<Emphasis Type="Italic">c</Emphasis>*-Supplemented subgroups and <Emphasis Type="Italic">p</Emphasis>-nilpotency of finite groups

A subgroup H of a finite group G is said to be c*-supplemented in G if there exists a subgroup K such that G = HK and H ⋂ K is permutable in G. It is proved that a finite group G that is S ₄-free is p-nilpotent if N _G (P) is p-nilpotent and, for all x ∈ G\N _G (P), every minimal subgroup of is c*-supplemented in P and (if p = 2) one of the following conditions is satisfied: (a) every cyclic subgroup of of order 4 is c*-supplemented in P, (b) , (c) P is quaternion-free, where P a Sylow p-subgroup of G and is the p-nilpotent residual of G. This extends and improves some known results. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1011–1019, August, 2007.     

Distance-2-Matchings of Random Graphs

In this paper we study the maximal size of a distance-2-matching in a random graph G _n;M , i.e., the probability space consisting of subgraphs of the complete graph over n vertices, K _n , having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M ₂, is a set of Y-edges with the property that for any two elements every pair of their 4 incident vertices has Y-distance 2. Let M₂(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M₂(Y) and a sharp concentration result for the random variable AMS Subject Classification: 05C80, 05C70.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Exact asymptotic behaviour of the codimensions of some P.I. algebras

Letc _n (A) denote the codimensions of a P.I. algebraA, and assumec _n (A) has a polynomial growth: . Then, necessarily,q∈ℚ [D3]. If 1∈A, we show that , wheree=2.71…. In the non-unitary case, for any 0<q∈ℚ, we constructA, with a suitablek, such that . In memory of S. A. Amitsur, our teacher and friend Partially supported by Grant MM404/94 of Ministry of Education and Science, Bulgaria and by a Bulgarian-American Grant of NSF. Partially supported by NSF grant DMS-9101488.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

Characterization of Amalgamated Free Blocks of a Graph von Neumann Algebra

We identify two noncommutative structures naturally associated with countable directed graphs. They are formulated in the language of operators on Hilbert spaces. If G is a countable directed graphs with its vertex set V(G) and its edge set E(G), then we associate partial isometries to the edges in E(G) and projections to the vertices in V(G). We construct a corresponding von Neumann algebra as a groupoid crossed product algebra of an arbitrary fixed von Neumann algebra M and the graph groupoid induced by G, via a graph-representation (or a groupoid action) α. Graph groupoids are well-determined (categorial) groupoids. The graph groupoid of G has its binary operation, called admissibility. This has concrete local parts , for all e ∈ E(G). We characterize of , induced by the local parts of , for all e ∈ E(G). We then characterize all amalgamated free blocks of . They are chracterized by well-known von Neumann algebras: the classical group crossed product algebras , and certain subalgebras (M) of operator-valued matricial algebra . This shows that graph von Neumann algebras identify the key properties of graph groupoids. Received: December 20, 2006. Revised: March 07, 2007. Accepted: March 13, 2007.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.