Studies on some graph operators and related topics

Department of Mathematics, Cochin University of Science and Technology

GALLAI AND ANTI-GALLAI GRAPHS OF A GRAPH

Abstract. The paper deals with graph operators-the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H-free for any finite graph H. The case of complement reducible graphs-cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.

Applications of graph transformation in tools for domain-specific modeling languages

The use of domain-specific languages (DSLs) has been proposed as an approach to cost-e ectively develop families of software systems in a restricted application domain. Domain-specific languages in combination with the accumulated knowledge and experience of previous implementations, can in turn be used to generate new applications with unique sets of requirements. For this reason, DSLs are considered to be an important approach for software reuse. However, the toolset supporting a particular domain-specific language is also domain-specific and is per definition not reusable. Therefore, creating and maintaining a DSL requires additional resources that could be even larger than the savings associated with using them. As a solution, di erent tool frameworks have been proposed to simplify and reduce the cost of developments of DSLs. Developers of tool support for DSLs need to instantiate, customize or configure the framework for a particular DSL. There are di erent approaches for this. An approach is to use an application programming interface (API) and to extend the basic framework using an imperative programming language. An example of a tools which is based on this approach is Eclipse GEF. Another approach is to configure the framework using declarative languages that are independent of the underlying framework implementation. We believe this second approach can bring important benefits as this brings focus to specifying what should the tool be like instead of writing a program specifying how the tool achieves this functionality. In this thesis we explore this second approach. We use graph transformation as the basic approach to customize a domain-specific modeling (DSM) tool framework. The contributions of this thesis includes a comparison of di erent approaches for defining, representing and interchanging software modeling languages and models and a tool architecture for an open domain-specific modeling framework that e ciently integrates several model transformation components and visual editors. We also present several specific algorithms and tool components for DSM framework. These include an approach for graph query based on region operators and the star operator and an approach for reconciling models and diagrams after executing model transformation programs. We exemplify our approach with two case studies MICAS and EFCO. In these studies we show how our experimental modeling tool framework has been used to define tool environments for domain-specific languages.

Spectral theory of differential operators on finite metric graphs and on bounded domains

Die vorliegende Arbeit widmet sich der Spektraltheorie von Differentialoperatoren auf metrischen Graphen und von indefiniten Differentialoperatoren auf beschränkten Gebieten. Sie besteht aus zwei Teilen. Im Ersten werden endliche, nicht notwendigerweise kompakte, metrische Graphen und die Hilberträume von quadratintegrierbaren Funktionen auf diesen betrachtet. Alle quasi-m-akkretiven Laplaceoperatoren auf solchen Graphen werden charakterisiert, und Abschätzungen an die negativen Eigenwerte selbstadjungierter Laplaceoperatoren werden hergeleitet. Weiterhin wird die Wohlgestelltheit eines gemischten Diffusions- und Transportproblems auf kompakten Graphen durch die Anwendung von Halbgruppenmethoden untersucht. Eine Verallgemeinerung des indefiniten Operators $-tfrac{d}{dx}sgn(x)tfrac{d}{dx}$ von Intervallen auf metrische Graphen wird eingeführt. Die Spektral- und Streutheorie der selbstadjungierten Realisierungen wird detailliert besprochen. Im zweiten Teil der Arbeit werden Operatoren untersucht, die mit indefiniten Formen der Art $langlegrad v, A(cdot)grad urangle$ mit $u,vin H_0^1(Omega)subset L^2(Omega)$ und $OmegasubsetR^d$ beschränkt, assoziiert sind. Das Eigenwertverhalten entspricht in Dimension $d=1$ einer verallgemeinerten Weylschen Asymptotik und für $dgeq 2$ werden Abschätzungen an die Eigenwerte bewiesen. Die Frage, wann indefinite Formmethoden für Dimensionen $dgeq 2$ anwendbar sind, bleibt offen und wird diskutiert.

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Attributed graph similarity from the quantum Jensen-Shannon divergence

One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach. © 2013 Springer-Verlag.

Spectral graph theory with applications to quantum adiabatic optimization

In this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.

A NEW PROOF OF OKAJI'S THEOREM FOR A CLASS OF SUM OF SQUARES OPERATORS

Let P be a linear partial differential operator with analytic coefficients. We assume that P is of the form ""sum of squares"", satisfying Hormander's bracket condition. Let q be a characteristic point; for P. We assume that q lies on a symplectic Poisson stratum of codimension two. General results of Okaji Show that P is analytic hypoelliptic at q. Hence Okaji has established the validity of Treves' conjecture in the codimension two case. Our goal here is to give a simple, self-contained proof of this fact.

COMPLETE ISOMORPHIC CLASSIFICATIONS OF SOME SPACES OF COMPACT OPERATORS

This paper is a continuation and a complement of our previous work on isomorphic classification of some spaces of compact operators. We improve the main result concerning extensions of the classical isomorphic classification of the Banach spaces of continuous functions on ordinals. As an application, fixing an ordinal a and denoting by X(xi), omega(alpha) <= xi < omega(alpha+1), the Banach space of all X-valued continuous functions defined in the interval of ordinals [0,xi] and equipped with the supremum, we provide complete isomorphic classifications of some Banach spaces K(X(xi),Y(eta)) of compact operators from X(xi) to Y(eta), eta >= omega. It is relatively consistent with ZFC (Zermelo-Fraenkel set theory with the axiom of choice) that these results include the following cases: 1.X* contains no copy of c(0) and has the Mazur property, and Y = c(0)(J) for every set J. 2. X = c(0)(I) and Y = l(q)(J) for any infinite sets I and J and 1 <= q < infinity. 3. X = l(p)(I) and Y = l(q)(J) for any infinite sets I and J and 1 <= q < p < infinity.

ON ISOMORPHIC CLASSIFICATIONS OF SPACES OF COMPACT OPERATORS

We prove an extension of the classical isomorphic classification of Banach spaces of continuous functions on ordinals. As a consequence, we give complete isomorphic classifications of some Banach spaces K(X,Y(n)), eta >= omega, of compact operators from X to Y(eta), the space of all continuous Y-valued functions defined in the interval of ordinals [1, eta] and equipped with the supremum norm. In particular, under the Continuum Hypothesis, we extend a recent result of C. Samuel by classifying, up to isomorphism, the spaces K(X(xi), c(0)(Gamma)(eta)), where omega <= xi < omega(1,) eta >= omega, Gamma is a countable set, X contains no complemented copy of l(1), X* has the Mazur property and the density character of X** is less than or equal to N(1).

Pseudodifferential operators with C*-algebra-valued symbols: Abstract characterizations

Given a separable unital C*-algebra C with norm parallel to center dot parallel to, let E-n denote the Banach-space completion of the C-valued Schwartz space on R-n with norm parallel to f parallel to(2)=parallel to < f, f >parallel to(1/2), < f, g >=integral f(x)* g(x)dx. The assignment of the pseudodifferential operator A=a(x,D) with C-valued symbol a(x,xi) to each smooth function with bounded derivatives a is an element of B-C(R-2n) defines an injective mapping O, from B-C(R-2n) to the set H of all operators with smooth orbit under the canonical action of the Heisenberg group on the algebra of all adjointable operators on the Hilbert module E-n. In this paper, we construct a left-inverse S for O and prove that S is injective if C is commutative. This generalizes Cordes' description of H in the scalar case. Combined with previous results of the second author, our main theorem implies that, given a skew-symmetric n x n matrix J and if C is commutative, then any A is an element of H which commutes with every pseudodifferential operator with symbol F(x+J xi), F is an element of B-C(R-n), is a pseudodifferential operator with symbol G(x - J xi), for some G is an element of B-C(R-n). That was conjectured by Rieffel.

ON SPACES OF COMPACT OPERATORS ON C(K, X) SPACES

This paper concerns the spaces of compact operators kappa(E,F), where E and F are Banach spaces C([1, xi], X) of all continuous X-valued functions defined on the interval of ordinals [1, xi] and equipped with the supremun norm. We provide sufficient conditions on X, Y, alpha, beta, xi and eta, with omega <= alpha <= beta < omega 1 for the following equivalence: (a) kappa(C([1, xi], X), C([1, alpha], Y)) is isomorphic to kappa(C([1,eta], X), C([1, beta], Y)), (b) beta < alpha(omega). In this way, we unify and extend results due to Bessaga and Pelczynski (1960) and C. Samuel (2009). Our result covers the case of the classical spaces X = l(p) and Y = l(q) with 1 < p, q < infinity.

Galerkin finite element method for incompressible thermofluid flows framed within the bond graph theory

In this paper a bond graph methodology is used to model incompressible fluid flows with viscous and thermal effects. The distinctive characteristic of these flows is the role of pressure, which does not behave as a state variable but as a function that must act in such a way that the resulting velocity field has divergence zero. Velocity and entropy per unit volume are used as independent variables for a single-phase, single-component flow. Time-dependent nodal values and interpolation functions are introduced to represent the flow field, from which nodal vectors of velocity and entropy are defined as state variables. The system for momentum and continuity equations is coincident with the one obtained by using the Galerkin method for the weak formulation of the problem in finite elements. The integral incompressibility constraint is derived based on the integral conservation of mechanical energy. The weak formulation for thermal energy equation is modeled with true bond graph elements in terms of nodal vectors of temperature and entropy rates, resulting a Petrov-Galerkin method. The resulting bond graph shows the coupling between mechanical and thermal energy domains through the viscous dissipation term. All kind of boundary conditions are handled consistently and can be represented as generalized effort or flow sources. A procedure for causality assignment is derived for the resulting graph, satisfying the Second principle of Thermodynamics. (C) 2007 Elsevier B.V. All rights reserved.

Optimization and Complexity Reduction of Switch-Reconfigured Antennas Using Graph Models

This letter addresses the optimization and complexity reduction of switch-reconfigured antennas. A new optimization technique based on graph models is investigated. This technique is used to minimize the redundancy in a reconfigurable antenna structure and reduce its complexity. A graph modeling rule for switch-reconfigured antennas is proposed, and examples are presented.