Sharif Digital Repository

The square G2 of a graph G is a graph with the same vertex set as G in which two vertices are joined by an edge if their distance in G is at most two. For a graph G, χ[G2), which is also known as the distance two coloring number of G is studied. We study coloring the square of grids Pm□Pn, cylinders Pm□C n, and tori Cm□Cn. For each m and n we determine χ((Pm□Pn)2), χ(P m□Cn)2), and in some cases χ((C m□Cn)2) while giving sharp bounds to the latter. We show that χ((Cm□Cn)2) is at most 8 except when m -n = 3, in which case the value is 9. Moreover, we conjecture that for every m (m ≥ 5) and n (n ≥ 5), we have, 5 ≤ χ((Cm□Cn)2) ≤ 7  

A set S of vertices of a graph G = (V, E) is a dominating set if every vertex of V(G) S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(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 domination number. Velammal in his Ph.D. thesis [Manonmaniam Sundaranar University, Tirunelveli, 1997] showed that for any tree T of order at least 3, 1 ≤ sdγ(T) ≤ 3. Furthermore, Aram, Favaron and Sheikholeslami, recently, in their paper entitled "Trees with domination subdivision number three," gave two characterizations of... 

Let G be a graph. A spanning subgraph of G is called a {1, 2}-factor if each of its components is a regular graph of degree one or two. In this paper we provide a short proof of a theorem of Tutte which says that a graph G has a {1, 2}-factor if and only if i(GS) ≤ |S| for any S ⊆ V(G), where i(GS) denotes the number of isolated vertices of GS  

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S.The total domination number γ<(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt(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 total domination number. We show that sdγt(G) ≤ n - γt(G) + 1 for any graph G of order n ≥ 3 and that sdγt(G) < n-γt(G) except if G ≃ P3, C3, K4, P6 or C6  

A Triangulated Irregular Network (TIN) is a data structure that is usually used for representing and storing monotone geographic surfaces, approximately. In this representation, the surface is approximated by a set of triangular faces whose projection on the XY-plane is a triangulation. The visibility graph of a TIN is a graph whose vertices correspond to the vertices of the TIN and there is an edge between two vertices if their corresponding vertices on TIN see each other, i.e. the segment that connects these vertices completely lies above the TIN. Computing the visibility graph of a TIN and its properties have been considered thoroughly in the literature. In this paper, we consider this... 

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R, we define G∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R∈ R, the graph G∩ R is a t-spanner for K(P) ∩ R, where K(P) is the complete geometric graph on P. For any set P of n points and any constant ε> 0 , we prove that P admits local (1 + ε) -spanners of sizes O(nlog 6n) and O(nlog n) w.r.t axis-parallel squares and vertical slabs,... 

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R, we define G∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R∈ R, the graph G∩ R is a t-spanner for K(P) ∩ R, where K(P) is the complete geometric graph on P. For any set P of n points and any constant ε> 0 , we prove that P admits local (1 + ε) -spanners of sizes O(nlog 6n) and O(nlog n) w.r.t axis-parallel squares and vertical slabs,... 

A lucky labeling of a graph G is a function l:V(G)→N, such that for every two adjacent vertices v and u of G, σ w∼vl(w)≠ σ w∼ul(w) (x∼y means that x is joined to y). A lucky number of G, denoted by η(G), is the minimum number k such that G has a lucky labeling l:V(G)→{1,⋯,k}. We prove that for a given planar 3-colorable graph G determining whether η(G)=2 is NP-complete. Also for every k≥2, it is NP-complete to decide whether η(G)=k for a given graph G  

For a graph G, let λ2(G) denote its second smallest Laplacian eigenvalue. It was conjectured that λ2(G)+λ2(G‾)≥1, where G‾ is the complement of G. In this paper, it is shown that max⁡{λ2(G),λ2(G‾)}≥[Formula presented]. © 2018 Elsevier Inc  

For a graph G of order n, let λ 2 (G) denote its second smallest Laplacian eigenvalue. It was conjectured that λ 2 (G)+λ 2 (G‾)≥1, where G‾ is the complement of G. For any x∈R n , let ∇ x ∈R (n2) be the vector whose {i,j}-th entry is |x i −x j |. In this paper, we show the aforementioned conjecture is equivalent to prove that every two orthonormal vectors f,g∈R n with zero mean satisfy ‖∇ f −∇ g ‖ 2 ≥2. In this article, it is shown that for the validity of the conjecture it suffices to prove that the conjecture holds for all permutation graphs. © 2019 Elsevier Inc  

A bipartite graph G = (A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v ? A, vertices adjacent to v are consecutive in B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G = (A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog3 n log log n) time and O(n) space, where n = |A|. This improves the current O(n 2) time bound available for the problem. We also show that for two special subclasses of convex... 

Let G be a graph of order n and γs′ (G) denote the signed edge domination number of G. In [B. Xu, Two classes of edge domination in graphs, Discrete Appl. Math. 154 (2006) 1541-1546] it was proved that for any graph G of order n, γs′ (G) ≤ ⌊ frac(11, 6) n - 1 ⌋. But the method given in the proof is not correct. In this paper we give an example for which the method of proof given in [1] does not work. © 2008 Elsevier B.V. All rights reserved  

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that ch2 (G) is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C5 and Δ (G) ≥ 3, then ch2 (G) ≤ Δ (G) + 1, where Δ (G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ2 (G) ≤ Δ (G) + 1. Among other results, we determine ch2... 

For a graph G, a zero-sum flow is an assignment of non-zero real numbers on the edges of G such that the total sum of all edges incident with any vertex of G is zero. A zero-sumk -flow for a graph G is a zero-sum flow with labels from the set {± 1, ..., ± (k - 1)}. In this paper for a graph G, a necessary and sufficient condition for the existence of zero-sum flow is given. We conjecture that if G is a graph with a zero-sum flow, then G has a zero-sum 6-flow. It is shown that the conjecture is true for 2-edge connected bipartite graphs, and every r-regular graph with r even, r > 2, or r = 3. © 2009 Elsevier Inc. All rights reserved  

A paired-dominating set of a graph G = (V, E) with no isolated vertex is a dominating set of vertices inducing a graph with a perfect matching. The paired-domination number of G, denoted by γp r (G), is the minimum cardinality of a paired-dominating set of G. We consider graphs of order n ≥ 6, minimum degree δ such that G and over(G, -) do not have an isolated vertex and we prove that. -if γp r (G) > 4 and γp r (over(G, -)) > 4, then γp r (G) + γp r (over(G, -)) ≤ 3 + min {δ (G), δ (over(G, -))}. -if δ (G) ≥ 2 and δ (over(G, -)) ≥ 2, then γp r (G) + γp r (over(G, -)) ≤ frac(2 n, 3) + 4 and γp r (G) + γp r (over(G, -)) ≤ frac(2 n, 3) + 2 if moreover n ≥ 21. © 2007 Elsevier B.V. All rights... 

The energy of a graph G, denoted by E (G), is defined as the sum of the absolute values of all eigenvalues of the adjacency matrix of G. It is proved that E (G) ≥ 2 (n - χ (over(G, -))) ≥ 2 (ch (G) - 1) for every graph G of order n, and that E (G) ≥ 2 ch (G) for all graphs G except for those in a few specified families, where over(G, -), χ (G), and ch (G) are the complement, the chromatic number, and the choice number of G, respectively. © 2007 Elsevier Inc. All rights reserved  

The minimum number of complete bipartite subgraphs needed to partition the edges of a graph G is denoted by b (G). A known lower bound on b (G) states that b (G) ≥max {p (G), q (G)}, where p (G) and q (G) are the numbers of positive and negative eigenvalues of the adjacency matrix of G, respectively. When equality is attained, G is said to be eigensharp and when b (G) = max {p (G), q (G)} + 1, G is called an almost eigensharp graph. In this paper, we investigate the eigensharpness of graphs with at most one cycle and products of some families of graphs. Among the other results, we show that Pm ∨ Pn, Cm ∨ Pn for m ≡ 2, 3 (mod 4) and Qn when n is odd are eigensharp. We obtain some results on... 

In this paper, we show that every (3k−3)-edge-connected graph G, under a certain degree condition, can be edge-decomposed into k factors G1,…,Gk such that for each vertex v∈V(Gi), |dGi(v)−dG(v)/k|<1, where 1≤i≤k. As an application, we deduce that every 6-edge-connected graph G can be edge-decomposed into three factors G1, G2, and G3 such that for each vertex v∈V(Gi) with 1≤i≤3, |dGi(v)−dG(v)/3|<1, unless G has exactly one vertex z with dG(z)⁄≡30. Next, we show that every odd-(3k−2)-edge-connected graph G can be edge-decomposed into k factors G1,…,Gk such that for each vertex v∈V(Gi), dGi(v) and dG(v) have the same parity and |dGi(v)−dG(v)/k|<2, where k is an odd positive integer and 1≤i≤k.... 

In [1], [2] it is shown that the minimum broadcast rate of a linear index code over a finite field Fq is equal to an algebraic invariant of the underlying digraph, called minrankq. In [3], it is proved that for F2 and any positive integer k, minrankq(G) ≤ k if and only if there exists a homomorphism from the complement of the graph G to the complement of a particular undirected graph family called 'graph family {Gk}'. As observed in [2], by combining these two results one can relate the linear index coding problem of undirected graphs to the graph homomorphism problem. In [4], a direct connection between linear index coding problem and graph homomorphism problem is introduced. In contrast to... 

A 2-hued coloring of a graph G is a coloring such that, for every vertex v∈V(G) of degree at least 2, the neighbors of v receive at least two colors. The smallest integer k such that G has a 2-hued coloring with k colors is called the 2-hued chromatic number of G, and is denoted by χ2(G). In this paper, we will show that, if G is a regular graph, then χ2(G)-χ(G)≤2log 2(α(G))+3, and, if G is a graph and δ(G)<2, then χ2(G)-χ(G)≤1+4 Δ2δ-1⌉(1+log 2Δ(G)2Δ(G)-δ(G)(α(G))), and in the general case, if G is a graph, then χ2(G)-χ(G)≤2+min α′(G),α(G)+ω(G)2