Sharif Digital Repository

In this paper, we apply some new algebraic no-homomorphism theorems in conjunction with some new chromatic parameters to estimate the circular chromatic number of graphs. To show the applicability of the general results, as a couple of examples, we generalize a well known inequality for the fractional chromatic number of graphs and we also show that the circular chromatic number of the graph obtained from the Petersen graph by excluding one vertex is equal to 3. Also, we focus on the Johnson-Holroyd-Stahl conjecture about the circular chromatic number of Kneser graphs and we propose an approach to this conjecture. In this regard, we introduce a new related conjecture on Kneser graphs and we... 

We introduce two necessary conditions for the existence of graph homomorphisms based on the concepts of density and power graph. As corollaries, we obtain a lower bound for the fractional chromatic number, and we set forward elementary proofs of the facts that the circular chromatic number of the Petersen graph is equal to three and the fact that the Coxeter graph is a core. © 2007 Elsevier B.V. All rights reserved  

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher's inequality for G-designs. © 2006 Elsevier Inc. All rights reserved  

In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff-Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem. As some applications, we obtain a necessary condition for the spanning subgraph problem, which also provides a generalization of a theorem of Mohar (1992) as a necessary condition for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge-transitive graph, we obtain theorems with a corollary about the existence of homomorphisms to cycles. This, specially, provides... 

In this paper we introduce a chromatic parameter, called the fixing chromatic number, which is related to unique colourability of graphs, in the sense that it measures how one can embed the given graph G in G∪Kt by adding edges between G and Kt to make the whole graph uniquely t-colourable. We study some basic properties of this parameter as well as its relationships to some other well-known chromatic numbers as the acyclic chromatic number. We compute the fixing chromatic number of some graph products by applying a modified version of the exponential graph construction. © 2005 Elsevier B.V. All rights reserved  

In this paper. 11This article is a revised version of Daneshgar and Hajiabolhassan (2008) [19] distributed on arXiv.org (1'st, Jan. 2008). we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the nth mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of n disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the nth isoperimetric constant and... 

Let G be a finite simple x-chromatic graph and L = {Lu} u∈V(G) be a list assignment to its vertices with Lu {1.....X}- A list colouring problem (G, L) with a unique solution for which the sum Σu∈V(G) |Lu| is maximized, is called a maximum X-list assignment of G. In this paper, we prove a Circuit Simulation Lemma that, strictly speaking, makes it possible to simulate any Boolean function by effective 3-colourings of a graph that is polynomial-time constructable from the Boolean function itself. We use the lemma to simply prove some old results as corollaries, and also we prove that the following decision problem, related to the computation of the fixing number of a graph [Daneshgar 1997,... 

In this paper, first we introduce the concept of a connected graph homomorphism as a homomorphism for which the inverse image of any edge is either empty or a connected graph, and then we concentrate on chromatically connected (resp. chromatically disconnected) graphs such as G for which any χ(G)-colouring is a connected (resp. disconnected) homomorphism to K χ(G). In this regard, we consider the relationships of the new concept to some other notions as uniquely-colourability. Also, we specify some classes of chromatically disconnected graphs such as Kneser graphs KG(m, n) for which m is sufficiently larger than n, and the line graphs of non-complete class II graphs. Moreover, we prove that... 

Let d (σ) stand for the defining number of the colouring σ. In this paper we consider dmin = minγ d (γ) and dmax = maxγ d (γ) for the onto χ-colourings γ of the circular complete graph Kn, d. In this regard we obtain a lower bound for dmin (Kn, d) and we also prove that this parameter is asymptotically equal to χ - 1. Also, we show that when χ ≥ 4 and s ≠ 0 then dmax (Kχ d - s, d) = χ + 2 s - 3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G. © 2006 Elsevier B.V. All rights reserved  

The basic goal of this article is to present an abstract system-theoretic approach to morphological filtering and the theory of translation invariant systems which is mainly based on residuated semigroups. Some new results as well as a number of basic questions are also introduced  

In a previous paper we introduced a generalized model for translation invariant (TI) operators. In this model we considered the space, φ of all maps from an abelian group G to ω U {-∞}, called LG-fuzzy sets, where ω is a complete lattice-ordered group; and we defined TI operators on this space. Also, in that paper, we proved strong reconstruction theorem to show the consistency of this model. This theorem states that for an order-preserving TI operator Y one can explicitly compute Y(A), for any A, from a specific subset of φ called the base of Y. In this paper duality is considered in the same general framework, and in this regard, continuous TI operators are studied. This kind of operators... 

We consider translation invariant (TI) operators on Φ, the set of maps from an abelian group G to Ω ∪ {−∞} , called LG-fuzzy sets, where 0 is a complete lattice ordered group. By defining Minkowski and morphological operations on Φ and considering order preserving operators, we prove a reconstruction theorem. This theorem, which is called the Strong Reconstruction Theorem (SRT), is similar to the Convolution Theorem in the theory of linear and shift invariant systems and states that for an order preserving TI operator Y one can explicitly compute Y ( A ), for any A , from a specific subset of Φ called the base of Y . The introduced framework is a general model for the theory of translation... 

The main goal of this paper is to verify classical properties of morphological operators within the general model of translation invariant (TI) systems. In this model, TI operators are defined on the space of LG-fuzzy sets Φ i.e. Φ = {A: G → Ω ∪ {− ∞}} in which G is an abelian group and Ω is a complete lattice ordered group. A TI operator Y is an operator on Φ which is invariant under translation on G and Ω as groups. We consider the generalization of Minkowski addition (D on Φ and we emphasize that (Φ,⊛) is an involutive residuated topological monoid. We verify all properties of traditional (set-theoretic) morphological operators as well as classical representations (Matheron, 1967) for... 

Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczyński [Some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733--748] introduced $e^{^{*}}(G)=|V(G)|(k-1)-{k \choose 2}$ as the minimum number of edges for a k-UCG and S. J. Xu [J. Combin. Theory Ser. B, 50 (1990), pp. 319--320] conjectured that any minimal k-UCG contains a Kk as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a k-UCG with clique number k-t, for each $t \geq 1$ and each k, when k is large enough. This also... 

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs  

Let d(σ)d(σ) stand for the defining number of the colouring σσ. In this paper we consider View the MathML sourcedmin=minγd(γ) and View the MathML sourcedmax=maxγd(γ) for the onto χχ-colourings γγ of the circular complete graph Kn,dKn,d. In this regard we obtain a lower bound for dmin(Kn,d)dmin(Kn,d) and we also prove that this parameter is asymptotically equal to χ-1χ-1. Also, we show that when χ⩾4χ⩾4 and s≠0s≠0 then dmax(Kχd-s,d)=χ+2s-3dmax(Kχd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G  

The development of an eco-friendly and cost-effective drug delivery system (DDS) remains a challenge in cancer treatment. This study suggests a novel, eco-friendly, and cost-effective method to synthesize aluminum fumarate (A520) MOF using tangerine peel extract (TPE) as a pH-sensitive coating agent on a reduced graphene oxide (rGO) substrate. The system also incorporates the 2,2′-bipyridine dimethyltin diisothiocyanate complex, (Sn(bpy), as an organotin complex) to enhance therapeutic efficacy while minimizing off-target effects. In vitro cellular and molecular cytotoxicity examinations were conducted using HEK-293 and MCF-7 cell lines to evaluate cytotoxicity after 24 and 72 h. The... 

Motivation: Tumor trees, which depict the evolutionary process of cancer, provide a backbone for discovering recurring evolutionary processes in cancer. While they are not the primary information extracted from genomic data, they are valuable for this purpose. One such extraction method involves summarizing multiple trees into a single representative tree, such as consensus trees or supertrees. Results: We define the “weighted centroid tree problem” to find the centroid tree of a set of single-labeled rooted trees through the following steps: (i) mapping the given trees into the Euclidean space, (ii) computing the weighted centroid matrix of the mapped trees, and (iii) finding the nearest... 

Consider the parameter Λ(G) = |E(G)| - |V(G)|(k - 1) + (k2) for a k-chromatic graph G, on the set of vertices V(G) and with the set of edges E(G). It is known that Λ(G)≥0 for any k-chromatic uniquely vertex-colourable graph G (k-UCG), and, S.J. Xu has conjectured that for any k-UCG, G, Λ(G) = 0 implies that cl(G) = k; in which cl(G) is the clique number of G. In this paper, first, we introduce the concept of the core of a k-UCG as an induced subgraph without any colour-class of size one, and without any vertex of degree k - 1. Considering (k, n)-cores as k-UCGs on n vertices, we show that edge-minimal (k, 2k)-cores do not exist when k ≥ 3, which shows that for any edge-minimal k-UCG on 2k... 

Hall's condition for the existence of a proper vertex list-multicoloring of a simple graph G has recently been used to define the fractional Hall and Hall-condition numbers of G, and . Little is known about , but it is known that , where ‘⩽’ means ‘is a subgraph of’ and α(H) denotes the vertex independence number of H. Let and denote the fractional chromatic and choice (list-chromatic) numbers of G. (Actually, Slivnik has shown that these are equal, but we will continue to distinguish notationally between them.) We give various relations among , , , and , mostly notably that , when G is a line graph. We give examples to show that this equality does not necessarily hold when G is...