WorldWideScience

Sample records for strong perfect graph

  1. Perfect secure domination in graphs

    Directory of Open Access Journals (Sweden)

    S.V. Divya Rashmi

    2017-07-01

    Full Text Available Let $G=(V,E$ be a graph. A subset $S$ of $V$ is a dominating set of $G$ if every vertex in $Vsetminus  S$ is adjacent to a vertex in $S.$ A dominating set $S$ is called a secure dominating set if for each $vin Vsetminus S$ there exists $uin S$ such that $v$ is adjacent to $u$ and $S_1=(Ssetminus{u}cup {v}$ is a dominating set. If further the vertex $uin S$ is unique, then $S$ is called a perfect secure dominating set. The minimum cardinality of a perfect secure dominating set of $G$ is called the perfect  secure domination number of $G$ and is denoted by $gamma_{ps}(G.$ In this paper we initiate a study of this parameter and present several basic results.

  2. On 4-critical t-perfect graphs

    OpenAIRE

    Benchetrit, Yohann

    2016-01-01

    It is an open question whether the chromatic number of $t$-perfect graphs is bounded by a constant. The largest known value for this parameter is 4, and the only example of a 4-critical $t$-perfect graph, due to Laurent and Seymour, is the complement of the line graph of the prism $\\Pi$ (a graph is 4-critical if it has chromatic number 4 and all its proper induced subgraphs are 3-colorable). In this paper, we show a new example of a 4-critical $t$-perfect graph: the complement of the line gra...

  3. Forbidden Structures for Planar Perfect Consecutively Colourable Graphs

    Directory of Open Access Journals (Sweden)

    Borowiecka-Olszewska Marta

    2017-05-01

    Full Text Available A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.

  4. Strongly 2-connected orientations of graphs

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2014-01-01

    We prove that a graph admits a strongly 2-connected orientation if and only if it is 4-edge-connected, and every vertex-deleted subgraph is 2-edge-connected. In particular, every 4-connected graph has such an orientation while no cubic 3-connected graph has such an orientation....

  5. Perfect 2-colorings of the generalized Petersen graph

    Indian Academy of Sciences (India)

    Perfect 2-colorings of the generalized Petersen graph. MEHDI ALAEIYAN and HAMED KARAMI. ∗. School of Mathematics, Iran University of Science and Technology,. Narmak, Tehran 16846, Iran. *Corresponding author. E-mail: alaeiyan@iust.ac.ir; h_karami@iust.ac.ir. MS received 24 November 2014; revised 26 April ...

  6. Strong sum distance in fuzzy graphs.

    Science.gov (United States)

    Tom, Mini; Sunitha, Muraleedharan Shetty

    2015-01-01

    In this paper the idea of strong sum distance which is a metric, in a fuzzy graph is introduced. Based on this metric the concepts of eccentricity, radius, diameter, center and self centered fuzzy graphs are studied. Some properties of eccentric nodes, peripheral nodes and central nodes are obtained. A characterisation of self centered complete fuzzy graph is obtained and conditions under which a fuzzy cycle is self centered are established. We have proved that based on this metric, an eccentric node of a fuzzy tree G is a fuzzy end node of G and a node is an eccentric node of a fuzzy tree if and only if it is a peripheral node of G and the center of a fuzzy tree consists of either one or two neighboring nodes. The concepts of boundary nodes and interior nodes in a fuzzy graph based on strong sum distance are introduced. Some properties of boundary nodes, interior nodes and complete nodes are studied.

  7. Perfect state transfer in unitary Cayley graphs over local rings

    Directory of Open Access Journals (Sweden)

    Yotsanan Meemark

    2014-12-01

    Full Text Available In this work, using eigenvalues and eigenvectors of unitary Cayley graphs over finite local rings and elementary linear algebra, we characterize which local rings allowing PST occurring in its unitary Cayley graph. Moreover, we have some developments when $R$ is a product of local rings.

  8. Perfect 2-colorings of the generalized Petersen graph

    Indian Academy of Sciences (India)

    There are no perfect 2-colorings of GP(n, 2) with the matrix A3. Proof. Suppose, contrary to our claim, there is a perfect 2-coloring of GP(n, 2) with the matrix A3. By Lemma 3.4, there are 2 vertices ai and bi, for some 0 ≤ i ≤ n−1, such that they are the same color. By symmetry, without loss of generality, we can assume T (a0) ...

  9. Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem.

    Science.gov (United States)

    Gysel, Rob; Gusfield, Dan

    2011-01-01

    The multistate perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data.

  10. Computational Comparison of Several Greedy Algorithms for the Minimum Cost Perfect Matching Problem on Large Graphs

    DEFF Research Database (Denmark)

    Wøhlk, Sanne; Laporte, Gilbert

    2017-01-01

    The aim of this paper is to computationally compare several algorithms for the Minimum Cost Perfect Matching Problem on an undirected complete graph. Our work is motivated by the need to solve large instances of the Capacitated Arc Routing Problem (CARP) arising in the optimization of garbage...

  11. Graph-based stochastic control with constraints: A unified approach with perfect and imperfect measurements

    KAUST Repository

    Agha-mohammadi, Ali-akbar

    2013-06-01

    This paper is concerned with the problem of stochastic optimal control (possibly with imperfect measurements) in the presence of constraints. We propose a computationally tractable framework to address this problem. The method lends itself to sampling-based methods where we construct a graph in the state space of the problem, on which a Dynamic Programming (DP) is solved and a closed-loop feedback policy is computed. The constraints are seamlessly incorporated to the control policy selection by including their effect on the transition probabilities of the graph edges. We present a unified framework that is applicable both in the state space (with perfect measurements) and in the information space (with imperfect measurements).

  12. The inverse strong non-split r-domination number of a graph ...

    African Journals Online (AJOL)

    In this paper, we define the notions of inverse strong non-split r-dominating set and inverse strong non-split r-domination number γ′snsr(G) of a graph G. We characterize graphs for which γsnsr(G) + γ′snsr(G) = n, where γsnsr(G) is the strong non-split r-domination number of G. We get many bounds on γ′snsr(G).

  13. Computing strong metric dimension of some special classes of graphs by genetic algorithms

    Directory of Open Access Journals (Sweden)

    Kratica Jozef

    2008-01-01

    Full Text Available In this paper we consider the NP-hard problem of determining the strong metric dimension of graphs. The problem is solved by a genetic algorithm that uses binary encoding and standard genetic operators adapted to the problem. This represents the first attempt to solve this problem heuristically. We report experimental results for the two special classes of ORLIB test instances: crew scheduling and graph coloring.

  14. The Multi-State Perfect Phylogeny Problem with missing and removable data: solutions via integer-programming and chordal graph theory.

    Science.gov (United States)

    Gusfield, Dan

    2010-03-01

    The Multi-State Perfect Phylogeny Problem is an extension of the Binary Perfect Phylogeny Problem, allowing characters to take on more than two states. In this article, we consider three problems that extend the utility of the multi-state perfect phylogeny model: (1) the Missing Data (MD) Problem, where some entries in the input are missing and the question is whether (bounded) values for the missing data can be imputed so that the resulting data has a multi-state perfect phylogeny; (2) the Character-Removal (CR) Problem, where we want to minimize the number of characters to remove from the data so that the resulting data has a multi-state perfect phylogeny; and (3) the Missing-Data Character-Removal (MDCR) Problem, where the input has missing data and we want to impute values for the missing data to minimize the solution to the resulting Character-Removal Problem. We discuss Integer Linear Programming (ILP) solutions to these problems for the special case of three, four, and five permitted states per character, and we report on extensive empirical testing of these solutions. Then we develop a general theory to solve the MD problem for an arbitrary number of permitted states, using chordal graph theory and results on minimal triangulation of non-chordal graphs. This establishes new necessary and sufficient conditions for the existence of a perfect phylogeny with (or without) missing data. We implement the general theory using integer linear programming, although other optimization methods are possible. We extensively explore the empirical behavior of the general solution, showing that the methods are very practical for data of size and complexity that is characteristic of many current applications in phylogenetics. Some of the empirical results for the MD problem with an arbitrary number of permitted states are very surprising, suggesting the existence of additional combinatorial structure in multi-state perfect phylogenies. Finally, we note some relationships

  15. Spectra of Graphs

    NARCIS (Netherlands)

    Brouwer, A.E.; Haemers, W.H.

    2012-01-01

    This book gives an elementary treatment of the basic material about graph spectra, both for ordinary, and Laplace and Seidel spectra. The text progresses systematically, by covering standard topics before presenting some new material on trees, strongly regular graphs, two-graphs, association

  16. Interaction Graphs: Graphings

    OpenAIRE

    Seiller, Thomas

    2014-01-01

    In two previous papers, we exposed a combinatorial approach to the program of Geometry of Interaction, a program initiated by Jean-Yves Girard. The strength of our approach lies in the fact that we interpret proofs by simpler structures - graphs - than Girard's constructions, while generalizing the latter since they can be recovered as special cases of our setting. This third paper extends this approach by considering a generalization of graphs named graphings, which is in some way a geometri...

  17. A study on vague graphs.

    Science.gov (United States)

    Rashmanlou, Hossein; Samanta, Sovan; Pal, Madhumangal; Borzooei, R A

    2016-01-01

    The main purpose of this paper is to introduce the notion of vague h-morphism on vague graphs and regular vague graphs. The action of vague h-morphism on vague strong regular graphs are studied. Some elegant results on weak and co weak isomorphism are derived. Also, [Formula: see text]-complement of highly irregular vague graphs are defined.

  18. Picture perfect

    DEFF Research Database (Denmark)

    Pless, Mette; Sørensen, Niels Ulrik

    towards a performance-culture, where it is through performing (perfectly), that one becomes acknowledged as a young person, and where top-performances and the ability to position oneself as a ’winner’ is accentuated in young people’s narratives (Sørensen et al 2013, Jackson 2006). In the paper we ask how...... – and to what extent – performance-culture, and following from this, the narrow concept of normality, is something that different young people relate and define themselves in relation to. At the same time we maintain a focus on how common social demands and structurations affect and are managed by different...

  19. Knot Graphs

    OpenAIRE

    Noble, S D; Welsh, D J A

    2000-01-01

    We consider the equivalence classes of graphs induced by the unsigned versions of the Reidemeister moves on knot diagrams. Any graph which is reducible by some finite sequence of these moves, to a graph with no edges is called a knot graph. We show that the class of knot graphs strictly contains the set of delta-wye graphs. We prove that the dimension of the intersection of the cycle and cocycle spaces is an effective numerical invariant of these classes.

  20. ON BIPOLAR SINGLE VALUED NEUTROSOPHIC GRAPHS

    OpenAIRE

    Broumi, Said; Talea, Mohamed; Bakali, Assia; Smarandache, Florentin

    2016-01-01

    In this article, we combine the concept of bipolar neutrosophic set and graph theory. We introduce the notions of bipolar single valued neutrosophic graphs, strong bipolar single valued neutrosophic graphs, complete bipolar single valued neutrosophic graphs, regular bipolar single valued neutrosophic graphs and investigate some of their related properties.

  1. Equipackable graphs

    DEFF Research Database (Denmark)

    Hartnell, B.L.; Vestergaard, Preben Dahl

    There are many results dealing with the problem of decomposing a fixed graph into isomorphic subgraphs. There has also been work on characterizing graphs with the property that one can delete the edges of a number of edge disjoint copies of the subgraph and, regardless of how that is done......, the graph that remains can still be decomposed (such graphs are called or ). In this paper we consider the follwing variation. Given a fixed graph H, determine which graphs (call them ) have the property that every edge disjoint packing with H is maximum. In the case that the graph H is isomorphic...... to the path on 3 nodes, we characterize the equipackable graphs of girth 5 or more. randomly packable randomly decomposable equipackable maximal...

  2. Equipackable graphs

    DEFF Research Database (Denmark)

    Vestergaard, Preben Dahl; Hartnell, Bert L.

    2006-01-01

    There are many results dealing with the problem of decomposing a fixed graph into isomorphic subgraphs. There has also been work on characterizing graphs with the property that one can delete the edges of a number of edge disjoint copies of the subgraph and, regardless of how that is done......, the graph that remains can still be decomposed (such graphs are called randomly packable or randomly decomposable). In this paper we consider the following variation. Given a fixed graph H, determine which graphs (call them equipackable) have the property that every maximal edge disjoint packing with H...... is maximum. In the case that the graph H is isomorphic to the path on 3 nodes, we characterize the equipackable graphs of girth 5 or more....

  3. Well-covered graphs and factors

    DEFF Research Database (Denmark)

    Randerath, Bert; Vestergaard, Preben D.

    2006-01-01

    A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has...... a perfect [1,2]-factor F_G, i.e. a spanning subgraph such that each component is 1-regular og 2-regular. Here, we characterize all well-covered graphs G satisfying α(G)=α(F_G) for some perfect [1,2]-factor F_G. This class contains all well-covered graphs G without isolated vertices of order n with α ≥ (n...... - 1)/2, and in particular all very well-covered graphs....

  4. Graph passing in graph transformation

    NARCIS (Netherlands)

    Ghamarian, A.H.; Rensink, Arend; Fish, Andrew; Lambers, Leen

    Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which

  5. Graph Passing in Graph Transformation

    NARCIS (Netherlands)

    Ghamarian, A.H.; Rensink, Arend

    2012-01-01

    Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which

  6. Graph Decompositions

    DEFF Research Database (Denmark)

    Merker, Martin

    The topic of this PhD thesis is graph decompositions. While there exist various kinds of decompositions, this thesis focuses on three problems concerning edgedecompositions. Given a family of graphs H we ask the following question: When can the edge-set of a graph be partitioned so that each part...... k(T)-edge-connected graph whose size is divisible by the size of T admits a T-decomposition. This proves a conjecture by Barát and Thomassen from 2006. Moreover, we introduce a new arboricity notion where we restrict the diameter of the trees in a decomposition into forests. We conjecture......-connected planar graph contains two edge-disjoint 18/19 -thin spanning trees. Finally, we make progress on a conjecture by Baudon, Bensmail, Przybyło, and Wozniak stating that if a graph can be decomposed into locally irregular graphs, then there exists such a decomposition with at most 3 parts. We show...

  7. Subgraph Enumeration in Massive Graphs

    DEFF Research Database (Denmark)

    Silvestri, Francesco

    We consider the problem of enumerating all instances of a given sample graph in a large data graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let $E$ be the number of edges in the data graph, $k=\\BO{1}$ be the number of vertexes in the sample graph, $B......$ be the block length, and $M$ be the main memory size. The main result of the paper is a randomized algorithm that enumerates all instances of the sample graph in $\\BO{E^{k/2}/\\left(BM^{k/2-1}\\right)}$ expected I/Os if the maximum vertex degree of the data graph is $\\sqrt{EM}$. Under some assumptions, the same...... bound also applies with high probability. Our algorithm is I/O optimal, in the worst-case, when the sample graph belongs to the Alon class, which includes cliques, cycles and every graph with a perfect matching: indeed, we show that any algorithm enumerating $T$ instances must always use $\\BOM...

  8. Everybody's Different Nobody's Perfect

    Science.gov (United States)

    Everybody's Different, Nobody's Perfect Todos somos diferentes, nadie es perfecto Preschool Edition Edición preescolar Adapted for young children from "Everybody's Different, Nobody's Perfect," by Irwin M. Siegel, M.D., ...

  9. Strong Arcwise Connectedness

    OpenAIRE

    Espinoza, Benjamin; Gartside, Paul; Kovan-Bakan, Merve; Mamatelashvili, Ana

    2012-01-01

    A space is `n-strong arc connected' (n-sac) if for any n points in the space there is an arc in the space visiting them in order. A space is omega-strong arc connected (omega-sac) if it is n-sac for all n. We study these properties in finite graphs, regular continua, and rational continua. There are no 4-sac graphs, but there are 3-sac graphs and graphs which are 2-sac but not 3-sac. For every n there is an n-sac regular continuum, but no regular continuum is omega-sac. There is an omega-sac ...

  10. Introduction to graph theory

    CERN Document Server

    Trudeau, Richard J

    1994-01-01

    Preface1. Pure Mathematics Introduction; Euclidean Geometry as Pure Mathematics; Games; Why Study Pure Mathematics?; What's Coming; Suggested Reading2. Graphs Introduction; Sets; Paradox; Graphs; Graph diagrams; Cautions; Common Graphs; Discovery; Complements and Subgraphs; Isomorphism; Recognizing Isomorphic Graphs; Semantics The Number of Graphs Having a Given nu; Exercises; Suggested Reading3. Planar Graphs Introduction; UG, K subscript 5, and the Jordan Curve Theorem; Are there More Nonplanar Graphs?; Expansions; Kuratowski's Theorem; Determining Whether a Graph is Planar or

  11. Interaction graphs

    DEFF Research Database (Denmark)

    Seiller, Thomas

    2016-01-01

    Interaction graphs were introduced as a general, uniform, construction of dynamic models of linear logic, encompassing all Geometry of Interaction (GoI) constructions introduced so far. This series of work was inspired from Girard's hyperfinite GoI, and develops a quantitative approach that should...... be understood as a dynamic version of weighted relational models. Until now, the interaction graphs framework has been shown to deal with exponentials for the constrained system ELL (Elementary Linear Logic) while keeping its quantitative aspect. Adapting older constructions by Girard, one can clearly define...... "full" exponentials, but at the cost of these quantitative features. We show here that allowing interpretations of proofs to use continuous (yet finite in a measure-theoretic sense) sets of states, as opposed to earlier Interaction Graphs constructions were these sets of states were discrete (and finite...

  12. Graph theory

    CERN Document Server

    Diestel, Reinhard

    2017-01-01

    This standard textbook of modern graph theory, now in its fifth edition, combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject with concise yet reliably complete proofs, while offering glimpses of more advanced methods in each field by one or two deeper results, again with proofs given in full detail. The book can be used as a reliable text for an introductory course, as a graduate text, and for self-study. From the reviews: “This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory.”Acta Scientiarum Mathematiciarum “Deep, clear, wonderful. This is a serious book about the heart of graph theory. It has depth and integrity. ”Persi Diaconis & Ron Graham, SIAM Review “The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theo...

  13. PERFECT DEMAND ILLUSION

    Directory of Open Access Journals (Sweden)

    Alexander Yu. Sulimov

    2015-01-01

    Full Text Available The article is devoted to technique «Perfect demand illusion», which allows to strengthen the competitive advantageof retailers. Also in the paper spells out the golden rules of visual merchandising.The definition of the method «Demand illusion», formulated the conditions of its functioning, and is determined by the mainhypothesis of the existence of this method.Furthermore, given the definition of the «Perfect demand illusion», and describes its additional conditions. Also spells out the advantages of the «Perfect demandillusion», before the «Demand illusion».

  14. Graph Theory in Paris : Conference in Memory of Claude Berge

    CERN Document Server

    Fonlupt, Jean; Fouquet, Jean-Luc; Fournier, Jean-Claude; Alfonsín, Jorge

    2007-01-01

    In July 2004, a conference on graph theory was held in Paris in memory of Claude Berge, one of the pioneers of the field. The event brought together many prominent specialists on topics, such as perfect graphs and matching theory, upon which Claude Berge's work has had a major impact. This volume includes contributions to these and other topics from many of the participants.

  15. Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs

    NARCIS (Netherlands)

    R.C. Laskar (R.C.); H.M. Mulder (Martyn); B. Novick (Beth)

    2011-01-01

    textabstractMaximal outerplanar graphs are characterized using three different classes of graphs. A path-neighborhood graph is a connected graph in which every neighborhood induces a path. The triangle graph $T(G)$ has the triangles of the graph $G$ as its vertices, two of these being adjacent

  16. Graph theory

    CERN Document Server

    Gould, Ronald

    2012-01-01

    This introduction to graph theory focuses on well-established topics, covering primary techniques and including both algorithmic and theoretical problems. The algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as advanced undergraduates and graduate students of topology, algebra, and matrix theory. Fundamental concepts and notation and elementary properties and operations are the first subjects, followed by examinations of paths and searching, trees, and networks. S

  17. Graphs & digraphs

    CERN Document Server

    Chartrand, Gary; Zhang, Ping

    2010-01-01

    Gary Chartrand has influenced the world of Graph Theory for almost half a century. He has supervised more than a score of Ph.D. dissertations and written several books on the subject. The most widely known of these texts, Graphs and Digraphs, … has much to recommend it, with clear exposition, and numerous challenging examples [that] make it an ideal textbook for the advanced undergraduate or beginning graduate course. The authors have updated their notation to reflect the current practice in this still-growing area of study. By the authors' estimation, the 5th edition is approximately 50% longer than the 4th edition. … the legendary Frank Harary, author of the second graph theory text ever produced, is one of the figures profiled. His book was the standard in the discipline for several decades. Chartrand, Lesniak and Zhang have produced a worthy successor.-John T. Saccoman, MAA Reviews, June 2012 (This book is in the MAA's basic library list.)As with the earlier editions, the current text emphasizes clear...

  18. CHARACTERISATION OF REGULAR GRAPHS AS LOOP GRAPHS ...

    African Journals Online (AJOL)

    There have been various generalisations of Cayley graphs, prototypes of transitive graphs. The most generalised is the description of graphs on general groupoids. What has clearly emerged in this exercise is that the philosophy of constructing graphs on groupoids offers a fruitful avenue from which we may understand ...

  19. De Bruijn graphs and DNA graphs

    NARCIS (Netherlands)

    Pendavingh, Rudi; Schuurman, Petra; Woeginger, Gerhard; Brandstädt, Andreas; Le, Van Bang

    2001-01-01

    In this paper we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs. In particular, the recognition of DNA graphs is shown to be NP-hard; DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. As a consequence, two open

  20. Graph theory

    CERN Document Server

    Diestel, Reinhard

    2012-01-01

    HauptbeschreibungThis standard textbook of modern graph theory, now in its fourth edition, combinesthe authority of a classic with the engaging freshness of style that is the hallmarkof active mathematics. It covers the core material of the subject with concise yetreliably complete proofs, while offering glimpses of more advanced methodsin each field by one or two deeper results, again with proofs given in full detail.The book can be used as a reliable text for an introductory course, as a graduatetext, and for self-study. Rezension"Deep, clear, wonderful. This is a serious book about the

  1. A Clustering Graph Generator

    Energy Technology Data Exchange (ETDEWEB)

    Winlaw, Manda [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); De Sterck, Hans [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Sanders, Geoffrey [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)

    2015-10-26

    In very simple terms a network can be de ned as a collection of points joined together by lines. Thus, networks can be used to represent connections between entities in a wide variety of elds including engi- neering, science, medicine, and sociology. Many large real-world networks share a surprising number of properties, leading to a strong interest in model development research and techniques for building synthetic networks have been developed, that capture these similarities and replicate real-world graphs. Modeling these real-world networks serves two purposes. First, building models that mimic the patterns and prop- erties of real networks helps to understand the implications of these patterns and helps determine which patterns are important. If we develop a generative process to synthesize real networks we can also examine which growth processes are plausible and which are not. Secondly, high-quality, large-scale network data is often not available, because of economic, legal, technological, or other obstacles [7]. Thus, there are many instances where the systems of interest cannot be represented by a single exemplar network. As one example, consider the eld of cybersecurity, where systems require testing across diverse threat scenarios and validation across diverse network structures. In these cases, where there is no single exemplar network, the systems must instead be modeled as a collection of networks in which the variation among them may be just as important as their common features. By developing processes to build synthetic models, so-called graph generators, we can build synthetic networks that capture both the essential features of a system and realistic variability. Then we can use such synthetic graphs to perform tasks such as simulations, analysis, and decision making. We can also use synthetic graphs to performance test graph analysis algorithms, including clustering algorithms and anomaly detection algorithms.

  2. Graph limits and hereditary properties

    OpenAIRE

    Janson, Svante

    2011-01-01

    We collect some general results on graph limits associated to hereditary classes of graphs. As examples, we consider some classes defined by forbidden subgraphs and some classes of intersection graphs, including triangle-free graphs, chordal graphs, cographs, interval graphs, unit interval graphs, threshold graphs, and line graphs.

  3. California's Perfect Storm

    Science.gov (United States)

    Bacon, David

    2010-01-01

    The United States today faces an economic crisis worse than any since the Great Depression of the 1930s. Nowhere is it sharper than in the nation's schools. Last year, California saw a perfect storm of protest in virtually every part of its education system. K-12 teachers built coalitions with parents and students to fight for their jobs and their…

  4. Chromatic graph theory

    CERN Document Server

    Chartrand, Gary; Rosen, Kenneth H

    2008-01-01

    Beginning with the origin of the four color problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. Introducing graph theory with a coloring theme, Chromatic Graph Theory explores connections between major topics in graph theory and graph colorings as well as emerging topics. This self-contained book first presents various fundamentals of graph theory that lie outside of graph colorings, including basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the text deals exclusively with graph colorings. It covers vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings. The authors also describe edge colorings, monochromatic and rainbow edge colorings, complete vertex colorings, several distinguishing vertex and edge colorings, and many distance-related vertex coloring...

  5. Perfect focusing fusion system

    International Nuclear Information System (INIS)

    Miyamoto, G.; Takeda, T.; Iwata, G.; Mori, S.; Inoue, K.; Tanaka, M.

    1994-01-01

    We propose new perfect focusing (perfo) fusion systems in which ion- or atom-beam is used as a target for the fusion reaction, and ions (perfo particles) of different species moving in the perfo field collide with them. The 'efficiency' defined as the ratio of the fusion energy output to the radiation loss is ∼300, ∼20, and ∼4 for the T+D, 3 He+D, and 11 B+H reactions, respectively. (author)

  6. Spatial legend compatibility within versus between graphs in multiple graph comprehension.

    Science.gov (United States)

    Riechelmann, Eva; Huestegge, Lynn

    2018-02-01

    Previous research has shown that spatial compatibility between the data region and the legend of a graph is beneficial for comprehension. However, in multiple graphs, data-legend compatibility can come at the cost of spatial between-graph legend incompatibility. Here we aimed at determining which type of compatibility is most important for performance: global (legend-legend) compatibility between graphs, or local (data-legend) compatibility within graphs. Additionally, a baseline condition (incompatible) was included. Participants chose one out of several line graphs from a multiple panel as the answer to a data-related question. Compatibility type and the number of graphs per panel were varied. Whereas Experiment 1 involved simple graphs with only two lines/legend entries within each graph, Experiment 2 explored more complex graphs. The results indicated that compatibility speeds up comprehension, at least when a certain threshold of graph complexity is exceeded. Furthermore, we found evidence for an advantage of local over global data-legend compatibility under specific conditions. Taken together, the results further support the idea that compatibility principles strongly determine the ease of integration processes in graph comprehension and should thus be considered in multiple-panel design.

  7. Near perfect optics

    Energy Technology Data Exchange (ETDEWEB)

    Goeke, R.; Farnsworth, A.V.; Neumann, C.C.; Sweatt, W.C.; Warren, M.E.; Weed, J.W.

    1996-06-01

    This report discusses a novel fabrication process to produce nearly perfect optics. The process utilizes vacuum deposition techniques to optimally modify polished optical substrate surfaces. The surface figure, i.e. contour of a polished optical element, is improved by differentially filling in the low spots on the surface using flux from a physical vapor deposition source through an appropriate mask. The process is expected to enable the manufacture of diffraction-limited optical systems for the UV, extreme UV, and soft X-ray spectral regions, which would have great impact on photolithography and astronomy. This same technique may also reduce the fabrication cost of visible region optics with aspheric surfaces.

  8. Building the perfect PC

    CERN Document Server

    Thompson, Robert Bruce

    2006-01-01

    This popular Build-It-Yourself (BIY) PC book covers everything you want to know about building your own system: Planning and picking out the right components, step-by-step instructions for assembling your perfect PC, and an insightful discussion of why you'd want to do it in the first place. Most big brand computers from HP, Dell and others use lower-quality components so they can meet their aggressive pricing targets. But component manufacturers also make high-quality parts that you can either purchase directly, or obtain through distributors and resellers. Consumers and corporations

  9. Components in time-varying graphs.

    Science.gov (United States)

    Nicosia, Vincenzo; Tang, John; Musolesi, Mirco; Russo, Giovanni; Mascolo, Cecilia; Latora, Vito

    2012-06-01

    Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.

  10. Graphs and matrices

    CERN Document Server

    Bapat, Ravindra B

    2014-01-01

    This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reo...

  11. Metamaterials for perfect absorption

    CERN Document Server

    Lee, Young Pak; Yoo, Young Joon; Kim, Ki Won

    2016-01-01

    This book provides a comprehensive overview of the theory and practical development of metamaterial-based perfect absorbers (MMPAs). It begins with a brief history of MMPAs which reviews the various theoretical and experimental milestones in their development. The theoretical background and fundamental working principles of MMPAs are then discussed, providing the necessary background on how MMPAs work and are constructed. There then follows a section describing how different MMPAs are designed and built according to the operating frequency of the electromagnetic wave, and how their behavior is changed. Methods of fabricating and characterizing MMPAs are then presented. The book elaborates on the performance and characteristics of MMPAs, including electromagnetically-induced transparency (EIT). It also covers recent advances in MMPAs and their applications, including multi-band, broadband, tunability, polarization independence and incidence independence. Suitable for graduate students in optical sciences and e...

  12. Perfect and imperfect states

    Directory of Open Access Journals (Sweden)

    Nikitović Aleksandar

    2013-01-01

    Full Text Available Early Greek ethics embodied in Cretan and Spartan mores, served as a model for Plato`s political theory. Plato theorized the contents of early Greek ethics, aspiring to justify and revitalize the fundamental principles of a traditional view of the world. However, according to Plato`s new insight, deed is further from the truth than a thought i.e. theory. The dorian model had to renounce its position to the perfect prototype of a righteous state, which is a result of the inner logic of philosophical theorizing in early Greek ethics. Prototype and model of philosophical reflection, in comparison to philosophical theory, becomes minor and deficient. Philosophical theorizing of early Greek ethics philosophically formatted Greek heritage, initiating substantial changes to the content of traditional ethics. Replacement of the myth with ontology, as a new foundation of politics, transformed early Greek ethics in various relevant ways. [Projekat Ministarstva nauke Republike Srbije, br. 179049

  13. Topics on tournaments in graph theory

    CERN Document Server

    Moon, John W

    2015-01-01

    Tournaments, in this context, are directed graphs ― an important and interesting topic in graph theory. This concise volume collects a substantial amount of information on tournaments from throughout the mathematical literature. Suitable for advanced undergraduate students of mathematics, the straightforward treatment requires a basic familiarity with finite mathematics. The fundamental definitions and results appear in the earlier sections, and most of the later sections can be read independently of each other. Subjects include irreducible and strong tournaments, cycles and strong subtourname

  14. Extending classical multirate signal processing theory to graphs

    Science.gov (United States)

    Teke, Oguzhan; Vaidyanathan, Palghat P.

    2017-08-01

    A variety of different areas consider signals that are defined over graphs. Motivated by the advancements in graph signal processing, this study first reviews some of the recent results on the extension of classical multirate signal processing to graphs. In these results, graphs are allowed to have directed edges. The possibly non-symmetric adjacency matrix A is treated as the graph operator. These results investigate the fundamental concepts for multirate processing of graph signals such as noble identities, aliasing, and perfect reconstruction (PR). It is shown that unless the graph satisfies some conditions, these concepts cannot be extended to graph signals in a simple manner. A structure called M-Block cyclic structure is shown to be sufficient to generalize the results for bipartite graphs on two-channels to M-channel filter banks. Many classical multirate ideas can be extended to graphs due to the unique eigenstructure of M-Block cyclic graphs. For example, the PR condition for filter banks on these graphs is identical to PR in classical theory, which allows the use of well-known filter bank design techniques. In order to utilize these results, the adjacency matrix of an M-Block cyclic graph should be given in the correct permutation. In the final part, this study proposes a spectral technique to identify the hidden M-Block cyclic structure from a graph with noisy edges whose adjacency matrix is given under a random permutation. Numerical simulation results show that the technique can recover the underlying M-Block structure in the presence of random addition and deletion of the edges.

  15. A Maximum Resonant Set of Polyomino Graphs

    Directory of Open Access Journals (Sweden)

    Zhang Heping

    2016-05-01

    Full Text Available A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P − K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P − K has a unique perfect matching.

  16. Perfect simulation of Hawkes processes

    DEFF Research Database (Denmark)

    Møller, Jesper; Rasmussen, Jakob Gulddahl

    their branching and conditional independence structure, useful approximations of the distribution function for the length of a cluster are derived. This is used to construct upper and lower processes for the perfect simulation algorithm. Examples of applications and empirical results are presented.......This article concerns a perfect simulation algorithm for unmarked and marked Hawkes processes. The usual stratihtforward simulation algorithm suffers from edge effects, whereas our perfect simulation algorithm does not. By viewing Hawkes processes as Poisson cluster processes and using...

  17. Perfect Taxation with Imperfect Competition

    OpenAIRE

    Alan J. Auerbach; James R. Hines Jr.

    2001-01-01

    This paper analyzes features of perfect taxation also known as optimal taxation when one or more private markets is imperfectly competitive. Governments with perfect information and access to lump-sum taxes can provide corrective subsidies that render outcomes efficient in the presence of imperfect competition. Relaxing either of these two conditions removes the government's ability to support efficient resource allocation and changes the perfect policy response. When governments cannot use l...

  18. Perfect extinction in subwavelength dual metallic transmitting gratings.

    Science.gov (United States)

    Estruch, Thomas; Jaeck, Julien; Pardo, Fabrice; Derelle, Sophie; Primot, Jérôme; Pelouard, Jean-Luc; Haidar, Riad

    2011-08-15

    We investigate the strong electromagnetic coupling that settles in dual metallic grating structures. This coupling is evidenced to lead to a perfect optical extinction in the transmission spectrum. The behavior of this perfect extinction that strongly depends on the longitudinal space and the lateral displacement between the two gratings can be explained by a simple model that describes the interference between a propagating mode and a couple of evanescent modes. The results show that the electromagnetic transmission of the structure can be tuned by controlling the position of this perfect transmission extinction and thus pave the way to new types of infrared tunable filters. © 2011 Optical Society of America

  19. Integral trees and integral graphs

    NARCIS (Netherlands)

    Wang, Ligong

    2005-01-01

    This monograph deals with integral graphs, Laplacian integral regular graphs, cospectral graphs and cospectral integral graphs. The organization of this work, which consists of eight chapters, is as follows.

  20. Similarity Measure of Graphs

    Directory of Open Access Journals (Sweden)

    Amine Labriji

    2017-07-01

    Full Text Available The topic of identifying the similarity of graphs was considered as highly recommended research field in the Web semantic, artificial intelligence, the shape recognition and information research. One of the fundamental problems of graph databases is finding similar graphs to a graph query. Existing approaches dealing with this problem are usually based on the nodes and arcs of the two graphs, regardless of parental semantic links. For instance, a common connection is not identified as being part of the similarity of two graphs in cases like two graphs without common concepts, the measure of similarity based on the union of two graphs, or the one based on the notion of maximum common sub-graph (SCM, or the distance of edition of graphs. This leads to an inadequate situation in the context of information research. To overcome this problem, we suggest a new measure of similarity between graphs, based on the similarity measure of Wu and Palmer. We have shown that this new measure satisfies the properties of a measure of similarities and we applied this new measure on examples. The results show that our measure provides a run time with a gain of time compared to existing approaches. In addition, we compared the relevance of the similarity values obtained, it appears that this new graphs measure is advantageous and  offers a contribution to solving the problem mentioned above.

  1. Distributed Graph Filters

    NARCIS (Netherlands)

    Loukas, A.

    2015-01-01

    We have recently seen a surge of research focusing on the processing of graph data. The emerging field of signal processing on graphs focuses on the extension of classical discrete signal processing techniques to the graph setting. Arguably, the greatest breakthrough of the field has been the

  2. The Shrikhande Graph

    Indian Academy of Sciences (India)

    IAS Admin

    graph. We also note before closing this general discus- sion that among the family of regular and connected graphs, the graphs in the family of SRGs are character- ized by having exactly three distinct eigenvalues of the adjacency matrix. The friendship theorem asserts that if friendship in a community is a symmetric relation ...

  3. Graphing Inequalities, Connecting Meaning

    Science.gov (United States)

    Switzer, J. Matt

    2014-01-01

    Students often have difficulty with graphing inequalities (see Filloy, Rojano, and Rubio 2002; Drijvers 2002), and J. Matt Switzer's students were no exception. Although students can produce graphs for simple inequalities, they often struggle when the format of the inequality is unfamiliar. Even when producing a correct graph of an…

  4. Universal quantum graphs.

    Science.gov (United States)

    Pluhař, Z; Weidenmüller, H A

    2014-04-11

    For time-reversal invariant graphs we prove the Bohigas-Giannoni-Schmit conjecture in its most general form: For graphs that are mixing in the classical limit, all spectral correlation functions coincide with those of the Gaussian orthogonal ensemble of random matrices. For open graphs, we derive the analogous identities for all S-matrix correlation functions.

  5. Graph bisection revisited

    NARCIS (Netherlands)

    Sotirov, Renata

    2017-01-01

    The graph bisection problem is the problem of partitioning the vertex set of a graph into two sets of given sizes such that the sum of weights of edges joining these two sets is optimized. We present a semidefinite programming relaxation for the graph bisection problem with a matrix variable of

  6. Hyperbolicity in median graphs

    Indian Academy of Sciences (India)

    If is hyperbolic, we denote by () the sharp hyperbolicity constant of , i.e., ( X ) = inf { ≥ 0 : X is − hyperbolic } . In this paper we study the hyperbolicity of median graphs and we also obtain some results about general hyperbolic graphs. In particular, we prove that a median graph is hyperbolic if and only if its ...

  7. Handbook of graph theory

    CERN Document Server

    Gross, Jonathan L

    2003-01-01

    The Handbook of Graph Theory is the most comprehensive single-source guide to graph theory ever published. Best-selling authors Jonathan Gross and Jay Yellen assembled an outstanding team of experts to contribute overviews of more than 50 of the most significant topics in graph theory-including those related to algorithmic and optimization approaches as well as ""pure"" graph theory. They then carefully edited the compilation to produce a unified, authoritative work ideal for ready reference.Designed and edited with non-experts in mind, the Handbook of Graph Theory makes information easy to fi

  8. Graphs and Homomorphisms

    CERN Document Server

    Hell, Pavol

    2004-01-01

    This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colourings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics.Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level an

  9. Methods of visualizing graphs

    Science.gov (United States)

    Wong, Pak C.; Mackey, Patrick S.; Perrine, Kenneth A.; Foote, Harlan P.; Thomas, James J.

    2008-12-23

    Methods for visualizing a graph by automatically drawing elements of the graph as labels are disclosed. In one embodiment, the method comprises receiving node information and edge information from an input device and/or communication interface, constructing a graph layout based at least in part on that information, wherein the edges are automatically drawn as labels, and displaying the graph on a display device according to the graph layout. In some embodiments, the nodes are automatically drawn as labels instead of, or in addition to, the label-edges.

  10. Simplicial complexes of graphs

    CERN Document Server

    Jonsson, Jakob

    2008-01-01

    A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics, including commutative algebra, geometry, and knot theory. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology. Many of the proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this volume also provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees; it is successfully applied to a large number of graph and digraph complexes.

  11. Perfect Octagon Quadrangle Systems with an upper C4-system and a large spectrum

    Directory of Open Access Journals (Sweden)

    Luigia Berardi

    2011-02-01

    Full Text Available An octagon quadrangle is the graph consisting of an 8-cycle (x1, x2,..., x8 with two additional chords: the edges {x1, x4} and {x5, x8}. An octagon quadrangle system of order ν and index λ [OQS] is a pair (X,H, where X is a finite set of ν vertices and H is a collection of edge disjoint octagon quadrangles (called blocks which partition the edge set of λKν defined on X. An octagon quadrangle system Σ=(X,H of order ν and index λ is said to be upper C4-perfect if the collection of all of the upper 4-cycles contained in the octagon quadrangles form a μ-fold 4-cycle system of order ν; it is said to be upper strongly perfect, if the collection of all of the upper 4-cycles contained in the octagon quadrangles form a μ-fold 4-cycle system of order ν and also the collection of all of the outside 8-cycles contained in the octagon quadrangles form a ρ-fold 8-cycle system of order ν. In this paper, the authors determine the spectrum for these systems, in the case that it is the largest possible.

  12. Graphes et décompositions

    OpenAIRE

    Bouvier, Tom

    2014-01-01

    In this thesis, we study some width parameters on graphs, beyond tree-width and clique-width. Our first investigation is a comparative study between the tree-width of a graph and the clique-width of the associated incidence graph, from which we extract some strong algorithmic results. Then we present a few structural properties over a recently defined width called special tree-width and which takes its definition through both tree-width and clique-width. Finally, we end our journey with a mor...

  13. Perfect simulation of Hawkes processes

    DEFF Research Database (Denmark)

    Møller, Jesper; Rasmussen, Jakob Gulddahl

    2005-01-01

    their branching and conditional independence structures, useful approximations of the distribution function for the length of a cluster are derived. This is used to construct upper and lower processes for the perfect simulation algorithm. A tail-lightness condition turns out to be of importance......Our objective is to construct a perfect simulation algorithm for unmarked and marked Hawkes processes. The usual straightforward simulation algorithm suffers from edge effects, whereas our perfect simulation algorithm does not. By viewing Hawkes processes as Poisson cluster processes and using...

  14. Graphing trillions of triangles.

    Science.gov (United States)

    Burkhardt, Paul

    2017-07-01

    The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed.

  15. Myth of the Perfect Family

    Science.gov (United States)

    ... Spread the Word Shop AAP Find a Pediatrician Family Life Medical Home Family Dynamics Adoption & Foster Care ... Español Text Size Email Print Share The "Perfect" Family Page Content Article Body Is there such a ...

  16. Introductory graph theory

    CERN Document Server

    Chartrand, Gary

    1984-01-01

    Graph theory is used today in the physical sciences, social sciences, computer science, and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively, and informative style. Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics. Ten major topics - profusely illustrated - include: Mathematical Models, Elementary Concepts of Grap

  17. Uncertain Graph Sparsification

    OpenAIRE

    Parchas, Panos; Papailiou, Nikolaos; Papadias, Dimitris; Bonchi, Francesco

    2016-01-01

    Uncertain graphs are prevalent in several applications including communications systems, biological databases and social networks. The ever increasing size of the underlying data renders both graph storage and query processing extremely expensive. Sparsification has often been used to reduce the size of deterministic graphs by maintaining only the important edges. However, adaptation of deterministic sparsification methods fails in the uncertain setting. To overcome this problem, we introduce...

  18. Pattern graph rewrite systems

    Directory of Open Access Journals (Sweden)

    Aleks Kissinger

    2014-03-01

    Full Text Available String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning about diagrammatic theories via graph rewrite systems. In this extended abstract, we show how the power of such rewrite systems can be greatly extended by introducing pattern graphs, which provide a means of expressing infinite families of rewrite rules where certain marked subgraphs, called !-boxes ("bang boxes", on both sides of a rule can be copied any number of times or removed. After reviewing the string graph formalism, we show how string graphs can be extended to pattern graphs and how pattern graphs and pattern rewrite rules can be instantiated to concrete string graphs and rewrite rules. We then provide examples demonstrating the expressive power of pattern graphs and how they can be applied to study interacting algebraic structures that are central to categorical quantum mechanics.

  19. Creating more effective graphs

    CERN Document Server

    Robbins, Naomi B

    2012-01-01

    A succinct and highly readable guide to creating effective graphs The right graph can be a powerful tool for communicating information, improving a presentation, or conveying your point in print. If your professional endeavors call for you to present data graphically, here's a book that can help you do it more effectively. Creating More Effective Graphs gives you the basic knowledge and techniques required to choose and create appropriate graphs for a broad range of applications. Using real-world examples everyone can relate to, the author draws on her years of experience in gr

  20. Loose Graph Simulations

    DEFF Research Database (Denmark)

    Mansutti, Alessio; Miculan, Marino; Peressotti, Marco

    2017-01-01

    We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly...... also problems which are “mixed” instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give...

  1. Graph factors modulo k

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2014-01-01

    We prove a general result on graph factors modulo k . A special case says that, for each natural number k , every (12k−7)-edge-connected graph with an even number of vertices contains a spanning subgraph in which each vertex has degree congruent to k modulo 2k.......We prove a general result on graph factors modulo k . A special case says that, for each natural number k , every (12k−7)-edge-connected graph with an even number of vertices contains a spanning subgraph in which each vertex has degree congruent to k modulo 2k....

  2. Functions and graphs

    CERN Document Server

    Gelfand, I M; Shnol, E E

    1969-01-01

    The second in a series of systematic studies by a celebrated mathematician I. M. Gelfand and colleagues, this volume presents students with a well-illustrated sequence of problems and exercises designed to illuminate the properties of functions and graphs. Since readers do not have the benefit of a blackboard on which a teacher constructs a graph, the authors abandoned the customary use of diagrams in which only the final form of the graph appears; instead, the book's margins feature step-by-step diagrams for the complete construction of each graph. The first part of the book employs simple fu

  3. Graph Generator Survey

    Energy Technology Data Exchange (ETDEWEB)

    Lothian, Joshua [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Powers, Sarah S. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Sullivan, Blair D. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Baker, Matthew B. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Schrock, Jonathan [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Poole, Stephen W. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)

    2013-10-01

    The benchmarking effort within the Extreme Scale Systems Center at Oak Ridge National Laboratory seeks to provide High Performance Computing benchmarks and test suites of interest to the DoD sponsor. The work described in this report is a part of the effort focusing on graph generation. A previously developed benchmark, SystemBurn, allowed the emulation of different application behavior profiles within a single framework. To complement this effort, similar capabilities are desired for graph-centric problems. This report examines existing synthetic graph generator implementations in preparation for further study on the properties of their generated synthetic graphs.

  4. Approximate von Neumann entropy for directed graphs.

    Science.gov (United States)

    Ye, Cheng; Wilson, Richard C; Comin, César H; Costa, Luciano da F; Hancock, Edwin R

    2014-05-01

    In this paper, we develop an entropy measure for assessing the structural complexity of directed graphs. Although there are many existing alternative measures for quantifying the structural properties of undirected graphs, there are relatively few corresponding measures for directed graphs. To fill this gap in the literature, we explore an alternative technique that is applicable to directed graphs. We commence by using Chung's generalization of the Laplacian of a directed graph to extend the computation of von Neumann entropy from undirected to directed graphs. We provide a simplified form of the entropy which can be expressed in terms of simple node in-degree and out-degree statistics. Moreover, we find approximate forms of the von Neumann entropy that apply to both weakly and strongly directed graphs, and that can be used to characterize network structure. We illustrate the usefulness of these simplified entropy forms defined in this paper on both artificial and real-world data sets, including structures from protein databases and high energy physics theory citation networks.

  5. Characterisations of Intersection Graphs by Vertex Orderings

    OpenAIRE

    Wood, David R.

    2004-01-01

    Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an application, it is proved that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.

  6. Groups, graphs and random walks

    CERN Document Server

    Salvatori, Maura; Sava-Huss, Ecaterina

    2017-01-01

    An accessible and panoramic account of the theory of random walks on groups and graphs, stressing the strong connections of the theory with other branches of mathematics, including geometric and combinatorial group theory, potential analysis, and theoretical computer science. This volume brings together original surveys and research-expository papers from renowned and leading experts, many of whom spoke at the workshop 'Groups, Graphs and Random Walks' celebrating the sixtieth birthday of Wolfgang Woess in Cortona, Italy. Topics include: growth and amenability of groups; Schrödinger operators and symbolic dynamics; ergodic theorems; Thompson's group F; Poisson boundaries; probability theory on buildings and groups of Lie type; structure trees for edge cuts in networks; and mathematical crystallography. In what is currently a fast-growing area of mathematics, this book provides an up-to-date and valuable reference for both researchers and graduate students, from which future research activities will undoubted...

  7. Color-induced graph colorings

    CERN Document Server

    Zhang, Ping

    2015-01-01

    A comprehensive treatment of color-induced graph colorings is presented in this book, emphasizing vertex colorings induced by edge colorings. The coloring concepts described in this book depend not only on the property required of the initial edge coloring and the kind of objects serving as colors, but also on the property demanded of the vertex coloring produced. For each edge coloring introduced, background for the concept is provided, followed by a presentation of results and open questions dealing with this topic. While the edge colorings discussed can be either proper or unrestricted, the resulting vertex colorings are either proper colorings or rainbow colorings. This gives rise to a discussion of irregular colorings, strong colorings, modular colorings, edge-graceful colorings, twin edge colorings and binomial colorings. Since many of the concepts described in this book are relatively recent, the audience for this book is primarily mathematicians interested in learning some new areas of graph colorings...

  8. On the Extremal Wiener Polarity Index of Hückel Graphs.

    Science.gov (United States)

    Wang, Hongzhuan

    2016-01-01

    Graphs are used to model chemical compounds and drugs. In the graphs, each vertex represents an atom of molecule and edges between the corresponding vertices are used to represent covalent bounds between atoms. The Wiener polarity index W p (G) of a graph G is the number of unordered pairs of vertices u, v of G such that the distance between u and v is equal to 3. The trees and unicyclic graphs with perfect matching, of which all vertices have degrees not greater than three, are referred to as the Hückel trees and unicyclic Hückel graphs, respectively. In this paper, we first consider the smallest and the largest Wiener polarity index among all Hückel trees on 2n vertices and characterize the corresponding extremal graphs. Then we obtain an upper and lower bound for the Wiener polarity index of unicyclic Hückel graphs on 2n vertices.

  9. Graphs Generated by Measures

    Directory of Open Access Journals (Sweden)

    A. Assari

    2016-01-01

    Full Text Available In this paper, a graph is assigned to any probability measure on the σ-algebra of Borel sets of a topological space. Using this construction, it is proved that given any number n (finite or infinite there exists a nonregular graph such that its clique, chromatic, and dominating number equals n.

  10. Graphing Electric Potential.

    Science.gov (United States)

    De Jong, Marvin L.

    1993-01-01

    Describes the powerful graphing ability of computer algebra systems (CAS) to create three-dimensional graphs or surface graphics of electric potentials. Provides equations along with examples of the printouts. Lists the programs Mathematica, Maple, Derive, Theorist, MathCad, and MATLAB as promising CAS systems. (MVL)

  11. Graph Transforming Java Data

    NARCIS (Netherlands)

    de Mol, M.J.; Rensink, Arend; Hunt, James J.

    This paper introduces an approach for adding graph transformation-based functionality to existing JAVA programs. The approach relies on a set of annotations to identify the intended graph structure, as well as on user methods to manipulate that structure, within the user’s own JAVA class

  12. Recognition of fractal graphs

    NARCIS (Netherlands)

    Perepelitsa, VA; Sergienko, [No Value; Kochkarov, AM

    1999-01-01

    Definitions of prefractal and fractal graphs are introduced, and they are used to formulate mathematical models in different fields of knowledge. The topicality of fractal-graph recognition from the point of view, of fundamental improvement in the efficiency of the solution of algorithmic problems

  13. Adventures in graph theory

    CERN Document Server

    Joyner, W David

    2017-01-01

    This textbook acts as a pathway to higher mathematics by seeking and illuminating the connections between graph theory and diverse fields of mathematics, such as calculus on manifolds, group theory, algebraic curves, Fourier analysis, cryptography and other areas of combinatorics. An overview of graph theory definitions and polynomial invariants for graphs prepares the reader for the subsequent dive into the applications of graph theory. To pique the reader’s interest in areas of possible exploration, recent results in mathematics appear throughout the book, accompanied with examples of related graphs, how they arise, and what their valuable uses are. The consequences of graph theory covered by the authors are complicated and far-reaching, so topics are always exhibited in a user-friendly manner with copious graphs, exercises, and Sage code for the computation of equations. Samples of the book’s source code can be found at github.com/springer-math/adventures-in-graph-theory. The text is geared towards ad...

  14. Packing Degenerate Graphs Greedily

    Czech Academy of Sciences Publication Activity Database

    Allen, P.; Böttcher, J.; Hladký, J.; Piguet, Diana

    2017-01-01

    Roč. 61, August (2017), s. 45-51 ISSN 1571-0653 R&D Projects: GA ČR GJ16-07822Y Institutional support: RVO:67985807 Keywords : tree packing conjecture * graph packing * graph processes Subject RIV: BA - General Mathematics OBOR OECD: Pure mathematics

  15. Graph Colouring Algorithms

    DEFF Research Database (Denmark)

    Husfeldt, Thore

    2015-01-01

    This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...

  16. Moment graphs and representations

    DEFF Research Database (Denmark)

    Jantzen, Jens Carsten

    2012-01-01

    Moment graphs and sheaves on moment graphs are basically combinatorial objects that have be used to describe equivariant intersectiion cohomology. In these lectures we are going to show that they can be used to provide a direct link from this cohomology to the representation theory of simple Lie...

  17. The stable subgroup graph

    Directory of Open Access Journals (Sweden)

    Behnaz Tolue

    2018-07-01

    Full Text Available In this paper we introduce stable subgroup graph associated to the group $G$. It is a graph with vertex set all subgroups of $G$ and two distinct subgroups $H_1$ and $H_2$ are adjacent if $St_{G}(H_1\\cap H_2\

  18. Generalized connectivity of graphs

    CERN Document Server

    Li, Xueliang

    2016-01-01

    Noteworthy results, proof techniques, open problems and conjectures in generalized (edge-) connectivity are discussed in this book. Both theoretical and practical analyses for generalized (edge-) connectivity of graphs are provided. Topics covered in this book include: generalized (edge-) connectivity of graph classes, algorithms, computational complexity, sharp bounds, Nordhaus-Gaddum-type results, maximum generalized local connectivity, extremal problems, random graphs, multigraphs, relations with the Steiner tree packing problem and generalizations of connectivity. This book enables graduate students to understand and master a segment of graph theory and combinatorial optimization. Researchers in graph theory, combinatorics, combinatorial optimization, probability, computer science, discrete algorithms, complexity analysis, network design, and the information transferring models will find this book useful in their studies.

  19. Product of Locally Primitive Graphs

    Directory of Open Access Journals (Sweden)

    Amir Assari

    2014-01-01

    Full Text Available Many large graphs can be constructed from existing smaller graphs by using graph operations, such as the product of two graphs. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this paper we consider the product of two locally primitive graphs and prove that only tensor product of them will also be locally primitive.

  20. Graph Abstraction and Abstract Graph Transformation

    NARCIS (Netherlands)

    Boneva, I.B.; Rensink, Arend; Kurban, M.E.; Bauer, J.

    2007-01-01

    Many important systems like concurrent heap-manipulating programs, communication networks, or distributed algorithms are hard to verify due to their inherent dynamics and unboundedness. Graphs are an intuitive representation of states of these systems, where transitions can be conveniently described

  1. Designing the ''perfect'' projection screen

    Science.gov (United States)

    Caulfield, H. John

    2005-07-01

    A perfect diffuser would place 100% of the light leaving the projector in that small region of space where there will be audience eyes to observe it. It would not allow light from sources other than the projector to reach the eyes from the screen. The screen should be affordably priced and cosmetically unremarkable, e.g. seamless. The image seen by any observer should be equally bright over the whole screen. I discuss a way to approximate the perfect projection screen using kinoform diffusers, a Fresnel lens and a mirrored surface.

  2. Subgraph detection using graph signals

    KAUST Repository

    Chepuri, Sundeep Prabhakar

    2017-03-06

    In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

  3. Extremal graph theory

    CERN Document Server

    Bollobas, Bela

    2004-01-01

    The ever-expanding field of extremal graph theory encompasses a diverse array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume, based on a series of lectures delivered to graduate students at the University of Cambridge, presents a concise yet comprehensive treatment of extremal graph theory.Unlike most graph theory treatises, this text features complete proofs for almost all of its results. Further insights into theory are provided by the numerous exercises of varying degrees of difficulty that accompany each chapter. A

  4. Application of Bipolar Fuzzy Sets in Graph Structures

    Directory of Open Access Journals (Sweden)

    Muhammad Akram

    2016-01-01

    Full Text Available A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we apply the concept of bipolar fuzzy sets to graph structures. We introduce certain notions, including bipolar fuzzy graph structure (BFGS, strong bipolar fuzzy graph structure, bipolar fuzzy Ni-cycle, bipolar fuzzy Ni-tree, bipolar fuzzy Ni-cut vertex, and bipolar fuzzy Ni-bridge, and illustrate these notions by several examples. We study ϕ-complement, self-complement, strong self-complement, and totally strong self-complement in bipolar fuzzy graph structures, and we investigate some of their interesting properties.

  5. Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

    DEFF Research Database (Denmark)

    Bensmail, Julien; Renault, Gabriel

    2016-01-01

    An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition E1∪E2∪⋯∪Ek of the edge set E(G) such that each Ei induces a locally irregular graph. It was recently...... conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most...... three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed...

  6. Cycles in graphs

    CERN Document Server

    Alspach, BR

    1985-01-01

    This volume deals with a variety of problems involving cycles in graphs and circuits in digraphs. Leading researchers in this area present here 3 survey papers and 42 papers containing new results. There is also a collection of unsolved problems.

  7. Tailored Random Graph Ensembles

    International Nuclear Information System (INIS)

    Roberts, E S; Annibale, A; Coolen, A C C

    2013-01-01

    Tailored graph ensembles are a developing bridge between biological networks and statistical mechanics. The aim is to use this concept to generate a suite of rigorous tools that can be used to quantify and compare the topology of cellular signalling networks, such as protein-protein interaction networks and gene regulation networks. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies of random graph ensembles constrained with degree distribution and degree-degree correlation. We also construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities which converges to a strictly uniform measure and is based on edge swaps that conserve all degrees. The acceptance probabilities can be generalized to define Markov chains that target any alternative desired measure on the space of directed or undirected graphs, in order to generate graphs with more sophisticated topological features.

  8. Learning Probabilistic Decision Graphs

    DEFF Research Database (Denmark)

    Jaeger, Manfred; Dalgaard, Jens; Silander, Tomi

    2004-01-01

    Probabilistic decision graphs (PDGs) are a representation language for probability distributions based on binary decision diagrams. PDGs can encode (context-specific) independence relations that cannot be captured in a Bayesian network structure, and can sometimes provide computationally more...

  9. Introduction to graph theory

    CERN Document Server

    Wilson, Robin J

    1985-01-01

    Graph Theory has recently emerged as a subject in its own right, as well as being an important mathematical tool in such diverse subjects as operational research, chemistry, sociology and genetics. This book provides a comprehensive introduction to the subject.

  10. Efficiently Controllable Graphs.

    Science.gov (United States)

    Gokler, Can; Lloyd, Seth; Shor, Peter; Thompson, Kevin

    2017-06-30

    We investigate graphs that can be disconnected into small components by removing a vanishingly small fraction of their vertices. We show that, when a controllable quantum network is described by such a graph and the gaps in eigenfrequencies and in transition frequencies are bounded exponentially in the number of vertices, the network is efficiently controllable, in the sense that universal quantum computation can be performed using a control sequence polynomial in the size of the network while controlling a vanishingly small fraction of subsystems. We show that networks corresponding to finite-dimensional lattices are efficiently controllable and explore generalizations to percolation clusters and random graphs. We show that the classical computational complexity of estimating the ground state of Hamiltonians described by controllable graphs is polynomial in the number of subsystems or qubits.

  11. Interaction Graphs: Exponentials

    OpenAIRE

    Seiller, Thomas

    2013-01-01

    This paper is the fourth of a series exposing a systematic combinatorial approach to Girard's Geometry of Interaction program. This program aims at obtaining particular realizability models for linear logic that accounts for the dynamics of cut-elimination. This fourth paper tackles the complex issue of defining exponential connectives in this framework. In order to succeed in this, we use the notion of graphings, a generalization of graphs which was defined in earlier work. We explain how we...

  12. Continuous Yao graphs

    DEFF Research Database (Denmark)

    Bakhshesh, Davood; Barba, Luis; Bose, Prosenjit

    2018-01-01

    In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points S⊂R2 and an angle 0Yao graph cY(θ) with vertex set S and angle θ as follows. For each p,q∈S, we add an edge from p to q in cY(θ) if there exists a cone with apex p...

  13. Uniform Single Valued Neutrosophic Graphs

    Directory of Open Access Journals (Sweden)

    S. Broumi

    2017-09-01

    Full Text Available In this paper, we propose a new concept named the uniform single valued neutrosophic graph. An illustrative example and some properties are examined. Next, we develop an algorithmic approach for computing the complement of the single valued neutrosophic graph. A numerical example is demonstrated for computing the complement of single valued neutrosophic graphs and uniform single valued neutrosophic graph.

  14. Local Interaction on Random Graphs

    Directory of Open Access Journals (Sweden)

    Hans Haller

    2010-08-01

    Full Text Available We analyze dynamic local interaction in population games where the local interaction structure (modeled as a graph can change over time: A stochastic process generates a random sequence of graphs. This contrasts with models where the initial interaction structure (represented by a deterministic graph or the realization of a random graph cannot change over time.

  15. Categorical constructions in graph theory

    Directory of Open Access Journals (Sweden)

    Richard T. Bumby

    1986-01-01

    Full Text Available This paper presents some graph-theoretic questions from the viewpoint of the portion of category theory which has become common knowledge. In particular, the reader is encouraged to consider whether there is only one natural category of graphs and how theories of directed graphs and undirected graphs are related.

  16. Commuting projections on graphs

    Energy Technology Data Exchange (ETDEWEB)

    Vassilevski, Panayot S. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States). Center for Applied Scientific Computing; Zikatanov, Ludmil T. [Pennsylvania State Univ., University Park, PA (United States). Dept. of Mathematics

    2013-02-19

    For a given (connected) graph, we consider vector spaces of (discrete) functions defined on its vertices and its edges. These two spaces are related by a discrete gradient operator, Grad and its adjoint, ₋Div, referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ2-projection QH onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π H from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π H and QH commute with the discrete divergence operator, i.e., we have div π H = QH div. The respective pair of coarse edge-space and coarse vertexspace offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples.

  17. Modern graph theory

    CERN Document Server

    Bollobás, Béla

    1998-01-01

    The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed ...

  18. Hierarchy of graph matchbox manifolds

    OpenAIRE

    Lukina, Olga

    2011-01-01

    We study a class of graph foliated spaces, or graph matchbox manifolds, initially constructed by Kenyon and Ghys. For graph foliated spaces we introduce a quantifier of dynamical complexity which we call its level. We develop the fusion construction, which allows us to associate to every two graph foliated spaces a third one which contains the former two in its closure. Although the underlying idea of the fusion is simple, it gives us a powerful tool to study graph foliated spaces. Using fusi...

  19. Linear representation of a graph

    Directory of Open Access Journals (Sweden)

    Eduardo Montenegro

    2019-10-01

    Full Text Available In this paper the linear representation of a graph is defined. A linear representation of a graph is a subgroup of $GL(p,\\mathbb{R}$, the group of invertible matrices of order $ p $ and real coefficients. It will be demonstrated that every graph admits a linear representation. In this paper, simple and finite graphs will be used, framed in the graphs theory's area

  20. Visible light broadband perfect absorbers

    Energy Technology Data Exchange (ETDEWEB)

    Jia, X. L.; Meng, Q. X.; Yuan, C. X.; Zhou, Z. X.; Wang, X. O., E-mail: wxo@hit.edu.cn [School of Science, Harbin Institute of Technology, Harbin 150001 (China)

    2016-03-15

    The visible light broadband perfect absorbers based on the silver (Ag) nano elliptical disks and holes array are studied using finite difference time domain simulations. The semiconducting indium silicon dioxide thin film is introduced as the space layer in this sandwiched structure. Utilizing the asymmetrical geometry of the structures, polarization sensitivity for transverse electric wave (TE)/transverse magnetic wave (TM) and left circular polarization wave (LCP)/right circular polarization wave (RCP) of the broadband absorption are gained. The absorbers with Ag nano disks and holes array show several peaks absorbance of 100% by numerical simulation. These simple and flexible perfect absorbers are particularly desirable for various potential applications including the solar energy absorber.

  1. Looking beyond the perfect lens

    International Nuclear Information System (INIS)

    Wee, W H; Pendry, J B

    2010-01-01

    The holy grail of imaging is the ability to see through anything. From the conservation of energy, we can easily see that to see through a lossy material would require lenses with gain. The aim of this paper therefore is to propose a simple scheme by which we can construct a general perfect lens, with gain-one that can restore both the phases and amplitudes of near and far fields.

  2. Proxy Graph: Visual Quality Metrics of Big Graph Sampling.

    Science.gov (United States)

    Nguyen, Quan Hoang; Hong, Seok-Hee; Eades, Peter; Meidiana, Amyra

    2017-06-01

    Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.

  3. Cellular Automata on Graphs: Topological Properties of ER Graphs Evolved towards Low-Entropy Dynamics

    Directory of Open Access Journals (Sweden)

    Marc-Thorsten Hütt

    2012-06-01

    Full Text Available Cellular automata (CA are a remarkably  efficient tool for exploring general properties of complex systems and spatiotemporal patterns arising from local rules. Totalistic cellular automata,  where the update  rules depend  only on the density of neighboring states, are at the same time a versatile  tool for exploring  dynamical  processes on graphs. Here we briefly review our previous results on cellular automata on graphs, emphasizing some systematic relationships between network architecture and dynamics identified in this way. We then extend the investigation  towards graphs obtained in a simulated-evolution procedure, starting from Erdő s–Rényi (ER graphs and selecting for low entropies of the CA dynamics. Our key result is a strong association of low Shannon entropies with a broadening of the graph’s degree distribution.

  4. Exciton condensation and perfect Coulomb drag.

    Science.gov (United States)

    Nandi, D; Finck, A D K; Eisenstein, J P; Pfeiffer, L N; West, K W

    2012-08-23

    Coulomb drag is a process whereby the repulsive interactions between electrons in spatially separated conductors enable a current flowing in one of the conductors to induce a voltage drop in the other. If the second conductor is part of a closed circuit, a net current will flow in that circuit. The drag current is typically much smaller than the drive current owing to the heavy screening of the Coulomb interaction. There are, however, rare situations in which strong electronic correlations exist between the two conductors. For example, double quantum well systems can support exciton condensates, which consist of electrons in one well tightly bound to holes in the other. 'Perfect' drag is therefore expected; a steady transport current of electrons driven through one quantum well should be accompanied by an equal current of holes in the other. Here we demonstrate this effect, taking care to ensure that the electron-hole pairs dominate the transport and that tunnelling of charge between the quantum wells, which can readily compromise drag measurements, is negligible. We note that, from an electrical engineering perspective, perfect Coulomb drag is analogous to an electrical transformer that functions at zero frequency.

  5. The STAPL Parallel Graph Library

    KAUST Repository

    Harshvardhan,

    2013-01-01

    This paper describes the stapl Parallel Graph Library, a high-level framework that abstracts the user from data-distribution and parallelism details and allows them to concentrate on parallel graph algorithm development. It includes a customizable distributed graph container and a collection of commonly used parallel graph algorithms. The library introduces pGraph pViews that separate algorithm design from the container implementation. It supports three graph processing algorithmic paradigms, level-synchronous, asynchronous and coarse-grained, and provides common graph algorithms based on them. Experimental results demonstrate improved scalability in performance and data size over existing graph libraries on more than 16,000 cores and on internet-scale graphs containing over 16 billion vertices and 250 billion edges. © Springer-Verlag Berlin Heidelberg 2013.

  6. Fundamentals of algebraic graph transformation

    CERN Document Server

    Ehrig, Hartmut; Prange, Ulrike; Taentzer, Gabriele

    2006-01-01

    Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool envir...

  7. Self-stabilizing mutual exclusion on directed graphs

    NARCIS (Netherlands)

    D. Alstein; J.H. Hoepman (Jaap-Henk); B.E. Olivier; P.I.A. van der Put

    1995-01-01

    textabstractThis paper investigates the complexity of self-stabilizing mutual exclusion protocols for distributed systems, where processors communicate through shared memory according to a strongly connected directed communication graph. Tchuente's approach of covering a network with one directed

  8. Quantitative graph theory mathematical foundations and applications

    CERN Document Server

    Dehmer, Matthias

    2014-01-01

    The first book devoted exclusively to quantitative graph theory, Quantitative Graph Theory: Mathematical Foundations and Applications presents and demonstrates existing and novel methods for analyzing graphs quantitatively. Incorporating interdisciplinary knowledge from graph theory, information theory, measurement theory, and statistical techniques, this book covers a wide range of quantitative-graph theoretical concepts and methods, including those pertaining to real and random graphs such as:Comparative approaches (graph similarity or distance)Graph measures to characterize graphs quantitat

  9. Profinite graphs and groups

    CERN Document Server

    Ribes, Luis

    2017-01-01

    This book offers a detailed introduction to graph theoretic methods in profinite groups and applications to abstract groups. It is the first to provide a comprehensive treatment of the subject. The author begins by carefully developing relevant notions in topology, profinite groups and homology, including free products of profinite groups, cohomological methods in profinite groups, and fixed points of automorphisms of free pro-p groups. The final part of the book is dedicated to applications of the profinite theory to abstract groups, with sections on finitely generated subgroups of free groups, separability conditions in free and amalgamated products, and algorithms in free groups and finite monoids. Profinite Graphs and Groups will appeal to students and researchers interested in profinite groups, geometric group theory, graphs and connections with the theory of formal languages. A complete reference on the subject, the book includes historical and bibliographical notes as well as a discussion of open quest...

  10. Graphs, groups and surfaces

    CERN Document Server

    White, AT

    1985-01-01

    The field of topological graph theory has expanded greatly in the ten years since the first edition of this book appeared. The original nine chapters of this classic work have therefore been revised and updated. Six new chapters have been added, dealing with: voltage graphs, non-orientable imbeddings, block designs associated with graph imbeddings, hypergraph imbeddings, map automorphism groups and change ringing.Thirty-two new problems have been added to this new edition, so that there are now 181 in all; 22 of these have been designated as ``difficult'''' and 9 as ``unsolved''''. Three of the four unsolved problems from the first edition have been solved in the ten years between editions; they are now marked as ``difficult''''.

  11. Critical phenomena at perfect and non-perfect surfaces

    International Nuclear Information System (INIS)

    Pleimling, M

    2004-01-01

    In the past, perfect surfaces have been shown to yield local critical behaviour that differs from bulk critical behaviour. On the other hand, surface defects, whether they are of natural origin or created artificially, are known to modify local quantities. It is therefore important to clarify whether these defects are relevant or irrelevant for the surface critical behaviour. The purpose of this review is two-fold. In the first part we summarize some of the important results on surface criticality at perfect surfaces. Special attention is thereby paid to new developments such as for example the study of the surface critical behaviour in systems with competing interactions or of surface critical dynamics. In the second part the effect of surface defects (presence of edges, steps, quenched randomness, lines of adatoms, regular geometric patterns) on local critical behaviour in semi-infinite systems and in thin films is discussed in detail. Whereas most of the defects commonly encountered are shown to be irrelevant, some notable exceptions are highlighted. It is shown furthermore that under certain circumstances non-universal local critical behaviour may be observed at surfaces. (topical review)

  12. Graph theory and interconnection networks

    CERN Document Server

    Hsu, Lih-Hsing

    2008-01-01

    The advancement of large scale integrated circuit technology has enabled the construction of complex interconnection networks. Graph theory provides a fundamental tool for designing and analyzing such networks. Graph Theory and Interconnection Networks provides a thorough understanding of these interrelated topics. After a brief introduction to graph terminology, the book presents well-known interconnection networks as examples of graphs, followed by in-depth coverage of Hamiltonian graphs. Different types of problems illustrate the wide range of available methods for solving such problems. The text also explores recent progress on the diagnosability of graphs under various models.

  13. Towards Scalable Graph Computation on Mobile Devices

    Science.gov (United States)

    Chen, Yiqi; Lin, Zhiyuan; Pienta, Robert; Kahng, Minsuk; Chau, Duen Horng

    2015-01-01

    Mobile devices have become increasingly central to our everyday activities, due to their portability, multi-touch capabilities, and ever-improving computational power. Such attractive features have spurred research interest in leveraging mobile devices for computation. We explore a novel approach that aims to use a single mobile device to perform scalable graph computation on large graphs that do not fit in the device's limited main memory, opening up the possibility of performing on-device analysis of large datasets, without relying on the cloud. Based on the familiar memory mapping capability provided by today's mobile operating systems, our approach to scale up computation is powerful and intentionally kept simple to maximize its applicability across the iOS and Android platforms. Our experiments demonstrate that an iPad mini can perform fast computation on large real graphs with as many as 272 million edges (Google+ social graph), at a speed that is only a few times slower than a 13″ Macbook Pro. Through creating a real world iOS app with this technique, we demonstrate the strong potential application for scalable graph computation on a single mobile device using our approach. PMID:25859564

  14. Towards Scalable Graph Computation on Mobile Devices.

    Science.gov (United States)

    Chen, Yiqi; Lin, Zhiyuan; Pienta, Robert; Kahng, Minsuk; Chau, Duen Horng

    2014-10-01

    Mobile devices have become increasingly central to our everyday activities, due to their portability, multi-touch capabilities, and ever-improving computational power. Such attractive features have spurred research interest in leveraging mobile devices for computation. We explore a novel approach that aims to use a single mobile device to perform scalable graph computation on large graphs that do not fit in the device's limited main memory, opening up the possibility of performing on-device analysis of large datasets, without relying on the cloud. Based on the familiar memory mapping capability provided by today's mobile operating systems, our approach to scale up computation is powerful and intentionally kept simple to maximize its applicability across the iOS and Android platforms. Our experiments demonstrate that an iPad mini can perform fast computation on large real graphs with as many as 272 million edges (Google+ social graph), at a speed that is only a few times slower than a 13″ Macbook Pro. Through creating a real world iOS app with this technique, we demonstrate the strong potential application for scalable graph computation on a single mobile device using our approach.

  15. Endomorphisms of graph algebras

    DEFF Research Database (Denmark)

    Conti, Roberto; Hong, Jeong Hee; Szymanski, Wojciech

    2012-01-01

    We initiate a systematic investigation of endomorphisms of graph C*-algebras C*(E), extending several known results on endomorphisms of the Cuntz algebras O_n. Most but not all of this study is focused on endomorphisms which permute the vertex projections and globally preserve the diagonal MASA D......_E of C*(E). Our results pertain both automorphisms and proper endomorphisms. Firstly, the Weyl group and the restricted Weyl group of a graph C*-algebra are introduced and investigated. In particular, criteria of outerness for automorphisms in the restricted Weyl group are found. We also show...

  16. Spectral radius of graphs

    CERN Document Server

    Stevanovic, Dragan

    2015-01-01

    Spectral Radius of Graphs provides a thorough overview of important results on the spectral radius of adjacency matrix of graphs that have appeared in the literature in the preceding ten years, most of them with proofs, and including some previously unpublished results of the author. The primer begins with a brief classical review, in order to provide the reader with a foundation for the subsequent chapters. Topics covered include spectral decomposition, the Perron-Frobenius theorem, the Rayleigh quotient, the Weyl inequalities, and the Interlacing theorem. From this introduction, the

  17. Handbook of graph grammars and computing by graph transformation

    CERN Document Server

    Engels, G; Kreowski, H J; Rozenberg, G

    1999-01-01

    Graph grammars originated in the late 60s, motivated by considerations about pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph grammars has grown quite impressively. Besides the aforementioned areas, it includes software specification and development, VLSI layout schemes, database design, modeling of concurrent systems, massively parallel computer architectures, logic programming, computer animation, developmental biology, music composition, visual languages, and many others.The area of graph grammars and graph tran

  18. Topics in graph theory graphs and their Cartesian product

    CERN Document Server

    Imrich, Wilfried; Rall, Douglas F

    2008-01-01

    From specialists in the field, you will learn about interesting connections and recent developments in the field of graph theory by looking in particular at Cartesian products-arguably the most important of the four standard graph products. Many new results in this area appear for the first time in print in this book. Written in an accessible way, this book can be used for personal study in advanced applications of graph theory or for an advanced graph theory course.

  19. Using Graph Transformations and Graph Abstractions for Software Verification

    NARCIS (Netherlands)

    Zambon, Eduardo; Rensink, Arend

    In this paper we describe our intended approach for the verification of software written in imperative programming languages. We base our approach on model checking of graph transition systems, where each state is a graph and the transitions are specified by graph transformation rules. We believe

  20. Robustness of random graphs based on graph spectra.

    Science.gov (United States)

    Wu, Jun; Barahona, Mauricio; Tan, Yue-Jin; Deng, Hong-Zhong

    2012-12-01

    It has been recently proposed that the robustness of complex networks can be efficiently characterized through the natural connectivity, a spectral property of the graph which corresponds to the average Estrada index. The natural connectivity corresponds to an average eigenvalue calculated from the graph spectrum and can also be interpreted as the Helmholtz free energy of the network. In this article, we explore the use of this index to characterize the robustness of Erdős-Rényi (ER) random graphs, random regular graphs, and regular ring lattices. We show both analytically and numerically that the natural connectivity of ER random graphs increases linearly with the average degree. It is also shown that ER random graphs are more robust than the corresponding random regular graphs with the same number of vertices and edges. However, the relative robustness of ER random graphs and regular ring lattices depends on the average degree and graph size: there is a critical graph size above which regular ring lattices are more robust than random graphs. We use our analytical results to derive this critical graph size as a function of the average degree.

  1. Codes related to line graphs of triangular graphs and permutation ...

    African Journals Online (AJOL)

    For any prime p, we consider p-ary linear codes obtained from the row span of incidence matrices of line graphs of triangular graphs and adjacency matrices of their line graphs. We determine parameters of the codes, their automorphism groups and exhibit permutation decoding sets (PD-sets) for partial permutation ...

  2. Generating perfect fluid spheres in general relativity

    International Nuclear Information System (INIS)

    Boonserm, Petarpa; Visser, Matt; Weinfurtner, Silke

    2005-01-01

    Ever since Karl Schwarzschild's 1916 discovery of the spacetime geometry describing the interior of a particular idealized general relativistic star--a static spherically symmetric blob of fluid with position-independent density--the general relativity community has continued to devote considerable time and energy to understanding the general-relativistic static perfect fluid sphere. Over the last 90 years a tangle of specific perfect fluid spheres has been discovered, with most of these specific examples seemingly independent from each other. To bring some order to this collection, in this article we develop several new transformation theorems that map perfect fluid spheres into perfect fluid spheres. These transformation theorems sometimes lead to unexpected connections between previously known perfect fluid spheres, sometimes lead to new previously unknown perfect fluid spheres, and in general can be used to develop a systematic way of classifying the set of all perfect fluid spheres

  3. Whole or incomplete: the myth of body perfection

    Directory of Open Access Journals (Sweden)

    Abha Khetarpal

    2017-08-01

    Full Text Available The media’s and society’s prejudice in favor of ‘ablesim’ propagates the myth of body perfection. As a result we pursue perfection – the concept of ableism invades our minds as well as our culture and we all succumb to it’s lure. Disability is socially constructed; it is ableism that compels people to believe that perfection is normal. This belief is nothing less than social oppression. Even the rehabilitation therapies send out strong signals that persons with disabilities are ‘deficient’ and ‘abnormal’, and that to become a "valued" person they would have to overcome their disabilities. Since the physical component of self-concept is important in maintenance of health and in identity formation, such pressures can lead to a distortion of self-concept. The desire for human perfection can lead to medical conditions such as obsessive compulsive disorder, anorexia nervosa, or depression. It can also impact our understanding of what it means to be human and what signifies a perfect or happy life. This article expounds on why we must achieve, value, and polish psychological maturity through awareness, self-regulation, and honesty.

  4. Visualizing automorphisms of graph algebras

    DEFF Research Database (Denmark)

    Avery, James Emil; Johansen, Rune; Szymanski, Wojciech

    2018-01-01

    Graph C*-algebras have been celebrated as C*-algebras that can be seen, because many important properties may be determined by looking at the underlying graph. This paper introduces the permutation graph for a permutative endomorphism of a graph C*-algebra as a labeled directed multigraph...... that gives a visual representation of the endomorphism and facilitates computations. Combinatorial criteria have previously been developed for deciding when such an endomorphism is an automorphism, but here the question is reformulated in terms of the permutation graph and new proofs are given. Furthermore......, it is shown how to use permutation graphs to efficiently generate exhaustive collections of permutative automorphisms. Permutation graphs provide a natural link to the textile systems representing induced endomorphisms on the edge shift of the given graph, and this allows the powerful tools of the theory...

  5. Canonical Graph Shapes

    NARCIS (Netherlands)

    Rensink, Arend; Schmidt, David

    2004-01-01

    Graphs are an intuitive model for states of a (software) system that include pointer structures | for instance, object-oriented programs. However, a naive encoding results in large individual states and large, or even unbounded, state spaces. As usual, some form of abstraction is necessary in order

  6. Canonical Graph Shapes

    NARCIS (Netherlands)

    Rensink, Arend; Schmidt, D.A.

    2004-01-01

    Abstract. Graphs are an intuitive model for states of a (software) system that include pointer structures — for instance, object-oriented programs. However, a naive encoding results in large individual states and large, or even unbounded, state spaces. As usual, some form of abstraction is necessary

  7. Layouts of Expander Graphs

    OpenAIRE

    Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R.

    2015-01-01

    Bourgain and Yehudayoff recently constructed $O(1)$-monotone bipartite expanders. By combining this result with a generalisation of the unraveling method of Kannan, we construct 3-monotone bipartite expanders, which is best possible. We then show that the same graphs admit 3-page book embeddings, 2-queue layouts, 4-track layouts, and have simple thickness 2. All these results are best possible.

  8. Quorum Colorings of Graphs

    NARCIS (Netherlands)

    S.M. Heditniemi (Sandra); R.C. Laskar (R.C.); H.M. Mulder (Martyn)

    2012-01-01

    textabstractLet $G = (V,E)$ be a graph. A partition $\\pi = \\{V_1, V_2, \\ldots, V_k \\}$ of the vertices $V$ of $G$ into $k$ {\\it color classes} $V_i$, with $1 \\leq i \\leq k$, is called a {\\it quorum coloring} if for every vertex $v \\in V$, at least half of the vertices in the closed neighborhood

  9. Cookies and Graphs

    Science.gov (United States)

    Cooper, Carol

    1975-01-01

    Teachers of an integrated elementary classroom used cookie-sharing time as a learning experience for students. Responsible for dividing varying amounts of cookies daily, the students learned to translate their experiences to graphs of differing sophistication and analyses. Further interpretation and application were done by individual students…

  10. Nested Term Graphs

    NARCIS (Netherlands)

    Grabmayer, C.A.; van Oostrom, V.

    2014-01-01

    We report on work in progress on `nested term graphs' for formalizing higher-order terms (e.g. finite or infinite lambda-terms), including those expressing recursion (e.g. terms in the lambda-calculus with letrec). The idea is to represent the nested scope structure of a higher-order term by a

  11. Decoding Codes on Graphs

    Indian Academy of Sciences (India)

    Home; Journals; Resonance – Journal of Science Education; Volume 8; Issue 9. Decoding Codes on Graphs - Low Density Parity Check Codes. A S Madhu Aditya Nori. General Article Volume 8 Issue 9 September 2003 pp 49-59. Fulltext. Click here to view fulltext PDF. Permanent link:

  12. Graph-theoretical exorcism

    Energy Technology Data Exchange (ETDEWEB)

    Simmons, G.J.

    1985-01-01

    Given a graph G and an ordering phi of the vertices, V(G), we define a parsimonious proper coloring (PPC) of V(G) under phi to be a proper coloring of V(G) in the order phi, where a new color is introduced only when a vertex cannot be properly colored in its order with any of the colors already used.

  13. Probability on graphs random processes on graphs and lattices

    CERN Document Server

    Grimmett, Geoffrey

    2018-01-01

    This introduction to some of the principal models in the theory of disordered systems leads the reader through the basics, to the very edge of contemporary research, with the minimum of technical fuss. Topics covered include random walk, percolation, self-avoiding walk, interacting particle systems, uniform spanning tree, random graphs, as well as the Ising, Potts, and random-cluster models for ferromagnetism, and the Lorentz model for motion in a random medium. This new edition features accounts of major recent progress, including the exact value of the connective constant of the hexagonal lattice, and the critical point of the random-cluster model on the square lattice. The choice of topics is strongly motivated by modern applications, and focuses on areas that merit further research. Accessible to a wide audience of mathematicians and physicists, this book can be used as a graduate course text. Each chapter ends with a range of exercises.

  14. Temporal Representation in Semantic Graphs

    Energy Technology Data Exchange (ETDEWEB)

    Levandoski, J J; Abdulla, G M

    2007-08-07

    A wide range of knowledge discovery and analysis applications, ranging from business to biological, make use of semantic graphs when modeling relationships and concepts. Most of the semantic graphs used in these applications are assumed to be static pieces of information, meaning temporal evolution of concepts and relationships are not taken into account. Guided by the need for more advanced semantic graph queries involving temporal concepts, this paper surveys the existing work involving temporal representations in semantic graphs.

  15. On dominator colorings in graphs

    Indian Academy of Sciences (India)

    Graph coloring and domination are two major areas in graph theory that have been ... independent set if no two vertices in S are adjacent. ... independent set. The corona G1 ◦ G2 of two graphs G1 and G2 is defined to be the graph. G obtained by taking one copy of G1 and |V(G1)| copies of G2, and then joining the i-th.

  16. Hamiltonian paths on Platonic graphs

    Directory of Open Access Journals (Sweden)

    Brian Hopkins

    2004-07-01

    Full Text Available We develop a combinatorial method to show that the dodecahedron graph has, up to rotation and reflection, a unique Hamiltonian cycle. Platonic graphs with this property are called topologically uniquely Hamiltonian. The same method is used to demonstrate topologically distinct Hamiltonian cycles on the icosahedron graph and to show that a regular graph embeddable on the 2-holed torus is topologically uniquely Hamiltonian.

  17. Nullspace embeddings for outerplanar graphs

    NARCIS (Netherlands)

    L. Lovász (László); A. Schrijver (Alexander)

    2017-01-01

    textabstractWe study relations between geometric embeddings of graphs and the spectrum of associated matrices, focusing on outerplanar embeddings of graphs. For a simple connected graph G=(V,E), we define a "good" G-matrix as a V×V matrix with negative entries corresponding to adjacent nodes, zero

  18. Nullspace embeddings for outerplanar graphs

    NARCIS (Netherlands)

    L. Lovász (László); A. Schrijver (Alexander); M. Loebl (Martin); J. Nešetřil (Jaroslav); R. Thomas (Robin)

    2017-01-01

    htmlabstractWe study relations between geometric embeddings of graphs and the spectrum of associated matrices, focusing on outerplanar embeddings of graphs. For a simple connected graph G = (V, E), we define a "good” G-matrix as a V × V matrix with negative

  19. Nullspace embeddings for outerplanar graphs

    NARCIS (Netherlands)

    Lovász, L.; Schrijver, A.; Loebl, M.; Nešetřil, J.; Thomas, R.

    2017-01-01

    We study relations between geometric embeddings of graphs and the spectrum of associated matrices, focusing on outerplanar embeddings of graphs. For a simple connected graph G = (V, E), we define a “good” G-matrix as a V × V matrix with negative entries corresponding to adjacent nodes, zero entries

  20. Pattern-Based Graph Abstraction

    NARCIS (Netherlands)

    Rensink, Arend; Zambon, Eduardo; Ehrig, H; Engels, G.; Kreowski, H.J.; Rozenberg, G.

    We present a new abstraction technique for the exploration of graph transformation systems with infinite state spaces. This technique is based on patterns, simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into pattern graphs, layered

  1. Generalised compositionality in graph transformation

    NARCIS (Netherlands)

    Ghamarian, A.H.; Rensink, Arend; Ehrig, H; Engels, G.; Kreowski, H.J.; Rozenberg, G.

    We present a notion of composition applying both to graphs and to rules, based on graph and rule interfaces along which they are glued. The current paper generalises a previous result in two different ways. Firstly, rules do not have to form pullbacks with their interfaces; this enables graph

  2. Kevin Bacon and Graph Theory

    Science.gov (United States)

    Hopkins, Brian

    2004-01-01

    The interconnected world of actors and movies is a familiar, rich example for graph theory. This paper gives the history of the "Kevin Bacon Game" and makes extensive use of a Web site to analyze the underlying graph. The main content is the classroom development of the weighted average to determine the best choice of "center" for the graph. The…

  3. Mining and Indexing Graph Databases

    Science.gov (United States)

    Yuan, Dayu

    2013-01-01

    Graphs are widely used to model structures and relationships of objects in various scientific and commercial fields. Chemical molecules, proteins, malware system-call dependencies and three-dimensional mechanical parts are all modeled as graphs. In this dissertation, we propose to mine and index those graph data to enable fast and scalable search.…

  4. Graph transformation tool contest 2008

    NARCIS (Netherlands)

    Rensink, Arend; van Gorp, Pieter

    This special section is the outcome of the graph transformation tool contest organised during the Graph-Based Tools (GraBaTs) 2008 workshop, which took place as a satellite event of the International Conference on Graph Transformation (ICGT) 2008. The contest involved two parts: three “off-line case

  5. Submanifolds weakly associated with graphs

    Indian Academy of Sciences (India)

    We establish an interesting link between differential geometry and graph theory by defining submanifolds weakly associated with graphs. We prove that, in a local sense, every submanifold satisfies such an association, and other general results. Finally, we study submanifolds associated with graphs either in low ...

  6. A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria

    Directory of Open Access Journals (Sweden)

    Góngora Pedro A.

    2015-09-01

    Full Text Available Consider games where players wish to minimize the cost to reach some state. A subgame-perfect Nash equilibrium can be regarded as a collection of optimal paths on such games. Similarly, the well-known state-labeling algorithm used in model checking can be viewed as computing optimal paths on a Kripke structure, where each path has a minimum number of transitions. We exploit these similarities in a common generalization of extensive games and Kripke structures that we name “graph games”. By extending the Bellman-Ford algorithm for computing shortest paths, we obtain a model-checking algorithm for graph games with respect to formulas in an appropriate logic. Hence, when given a certain formula, our model-checking algorithm computes the subgame-perfect Nash equilibrium (as opposed to simply determining whether or not a given collection of paths is a Nash equilibrium. Next, we develop a symbolic version of our model checker allowing us to handle larger graph games. We illustrate our formalism on the critical-path method as well as games with perfect information. Finally, we report on the execution time of benchmarks of an implementation of our algorithms

  7. Graph 500 on OpenSHMEM: Using a Practical Survey of Past Work to Motivate Novel Algorithmic Developments

    Energy Technology Data Exchange (ETDEWEB)

    Grossman, Max [Rice Univ., Houston, TX (United States); Pritchard Jr., Howard Porter [Los Alamos National Lab. (LANL), Los Alamos, NM (United States); Budimlic, Zoran [Rice Univ., Houston, TX (United States); Sarkar, Vivek [Rice Univ., Houston, TX (United States)

    2016-12-22

    Graph500 [14] is an effort to offer a standardized benchmark across large-scale distributed platforms which captures the behavior of common communicationbound graph algorithms. Graph500 differs from other large-scale benchmarking efforts (such as HPL [6] or HPGMG [7]) primarily in the irregularity of its computation and data access patterns. The core computational kernel of Graph500 is a breadth-first search (BFS) implemented on an undirected graph. The output of Graph500 is a spanning tree of the input graph, usually represented by a predecessor mapping for every node in the graph. The Graph500 benchmark defines several pre-defined input sizes for implementers to test against. This report summarizes investigation into implementing the Graph500 benchmark on OpenSHMEM, and focuses on first building a strong and practical understanding of the strengths and limitations of past work before proposing and developing novel extensions.

  8. Asteroidal Quadruples in non Rooted Path Graphs

    Directory of Open Access Journals (Sweden)

    Gutierrez Marisa

    2015-11-01

    Full Text Available A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.

  9. Localization in random bipartite graphs: Numerical and empirical study

    Science.gov (United States)

    Slanina, František

    2017-05-01

    We investigate adjacency matrices of bipartite graphs with a power-law degree distribution. Motivation for this study is twofold: first, vibrational states in granular matter and jammed sphere packings; second, graphs encoding social interaction, especially electronic commerce. We establish the position of the mobility edge and show that it strongly depends on the power in the degree distribution and on the ratio of the sizes of the two parts of the bipartite graph. At the jamming threshold, where the two parts have the same size, localization vanishes. We found that the multifractal spectrum is nontrivial in the delocalized phase, but still near the mobility edge. We also study an empirical bipartite graph, namely, the Amazon reviewer-item network. We found that in this specific graph the mobility edge disappears, and we draw a conclusion from this fact regarding earlier empirical studies of the Amazon network.

  10. The pursuit of perfect packing

    CERN Document Server

    Weaire, Denis

    2000-01-01

    In 1998 Thomas Hales dramatically announced the solution of a problem that has long teased eminent mathematicians: what is the densest possible arrangement of identical spheres? The Pursuit of Perfect Packing recounts the story of this problem and many others that have to do with packing things together. The examples are taken from mathematics, physics, biology, and engineering, including the arrangement of soap bubbles in foam, atoms in a crystal, the architecture of the bee''s honeycomb, and the structure of the Giant''s Causeway. Using an informal style and with key references, the book also includes brief accounts of the lives of many of the scientists who devoted themselves to problems of packing over many centuries, together with wry comments on their efforts. It is an entertaining introduction to the field for both specialists and the more general public.

  11. The pursuit of perfect packing

    CERN Document Server

    Weaire, Denis

    2008-01-01

    Coauthored by one of the creators of the most efficient space packing solution, the Weaire-Phelan structure, The Pursuit of Perfect Packing, Second Edition explores a problem of importance in physics, mathematics, chemistry, biology, and engineering: the packing of structures. Maintaining its mathematical core, this edition continues and revises some of the stories from its predecessor while adding several new examples and applications. The book focuses on both scientific and everyday problems ranging from atoms to honeycombs. It describes packing models, such as the Kepler conjecture, Voronoï decomposition, and Delaunay decomposition, as well as actual structure models, such as the Kelvin cell and the Weaire-Phelan structure. The authors discuss numerous historical aspects and provide biographical details on influential contributors to the field, including emails from Thomas Hales and Ken Brakke. With examples from physics, crystallography, engineering, and biology, this accessible and whimsical bo...

  12. Perfect Liberty or Natural Liberty?

    DEFF Research Database (Denmark)

    Jacobsen, Stefan Gaarsmand

    2012-01-01

    The article investigates the concept of natural order as it is used by François Quesnay and Adam Smith in their respective economic writings. While Smith used the concept only after having visited Quesnay and the Physiocrats in France in the 1760s, in The Wealth of Nations he sought to negotiate...... the meaning of what was “natural” about economic life. The Physiocrats believed it possible to identify a model or a perfect regime of natural order – an order that they in fact thought to exist and function in China due to a rigorous system of economic laws. Smith sided with contemporary critics...... successors in political economy, and the problem of ordering the society from the vantage point of an economic science was rephrased as a problem of combining the physiocratic metaphysics of natural order with the ‘business of the world’ as expounded by Smith....

  13. Complete graph model for community detection

    Science.gov (United States)

    Sun, Peng Gang; Sun, Xiya

    2017-04-01

    Community detection brings plenty of considerable problems, which has attracted more attention for many years. This paper develops a new framework, which tries to measure the interior and the exterior of a community based on a same metric, complete graph model. In particular, the exterior is modeled as a complete bipartite. We partition a network into subnetworks by maximizing the difference between the interior and the exterior of the subnetworks. In addition, we compare our approach with some state of the art methods on computer-generated networks based on the LFR benchmark as well as real-world networks. The experimental results indicate that our approach obtains better results for community detection, is capable of splitting irregular networks and achieves perfect results on the karate network and the dolphin network.

  14. A seminar on graph theory

    CERN Document Server

    Harary, Frank

    2015-01-01

    Presented in 1962-63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.Lectures by this volume's editor, Frank Harary, include ""Some Theorems and Concepts of Graph Theory,"" ""Topological Concepts in Graph Theory,"" ""Graphical Reconstruction,"" and other introduc

  15. Domination criticality in product graphs

    Directory of Open Access Journals (Sweden)

    M.R. Chithra

    2015-07-01

    Full Text Available A connected dominating set is an important notion and has many applications in routing and management of networks. Graph products have turned out to be a good model of interconnection networks. This motivated us to study the Cartesian product of graphs G with connected domination number, γc(G=2,3 and characterize such graphs. Also, we characterize the k−γ-vertex (edge critical graphs and k−γc-vertex (edge critical graphs for k=2,3 where γ denotes the domination number of G. We also discuss the vertex criticality in grids.

  16. Dynamic Representations of Sparse Graphs

    DEFF Research Database (Denmark)

    Brodal, Gerth Stølting; Fagerberg, Rolf

    1999-01-01

    We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst...... case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity....

  17. Graph Creation, Visualisation and Transformation

    Directory of Open Access Journals (Sweden)

    Maribel Fernández

    2010-03-01

    Full Text Available We describe a tool to create, edit, visualise and compute with interaction nets - a form of graph rewriting systems. The editor, called GraphPaper, allows users to create and edit graphs and their transformation rules using an intuitive user interface. The editor uses the functionalities of the TULIP system, which gives us access to a wealth of visualisation algorithms. Interaction nets are not only a formalism for the specification of graphs, but also a rewrite-based computation model. We discuss graph rewriting strategies and a language to express them in order to perform strategic interaction net rewriting.

  18. Graph Sampling for Covariance Estimation

    KAUST Repository

    Chepuri, Sundeep Prabhakar

    2017-04-25

    In this paper the focus is on subsampling as well as reconstructing the second-order statistics of signals residing on nodes of arbitrary undirected graphs. Second-order stationary graph signals may be obtained by graph filtering zero-mean white noise and they admit a well-defined power spectrum whose shape is determined by the frequency response of the graph filter. Estimating the graph power spectrum forms an important component of stationary graph signal processing and related inference tasks such as Wiener prediction or inpainting on graphs. The central result of this paper is that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the second-order statistics of the graph signal from the subsampled observations, and more importantly, without any spectral priors. To this end, both a nonparametric approach as well as parametric approaches including moving average and autoregressive models for the graph power spectrum are considered. The results specialize for undirected circulant graphs in that the graph nodes leading to the best compression rates are given by the so-called minimal sparse rulers. A near-optimal greedy algorithm is developed to design the subsampling scheme for the non-parametric and the moving average models, whereas a particular subsampling scheme that allows linear estimation for the autoregressive model is proposed. Numerical experiments on synthetic as well as real datasets related to climatology and processing handwritten digits are provided to demonstrate the developed theory.

  19. MISAGA: An Algorithm for Mining Interesting Subgraphs in Attributed Graphs.

    Science.gov (United States)

    He, Tiantian; Chan, Keith C C

    2017-04-25

    An attributed graph contains vertices that are associated with a set of attribute values. Mining clusters or communities, which are interesting subgraphs in the attributed graph is one of the most important tasks of graph analytics. Many problems can be defined as the mining of interesting subgraphs in attributed graphs. Algorithms that discover subgraphs based on predefined topologies cannot be used to tackle these problems. To discover interesting subgraphs in the attributed graph, we propose an algorithm called mining interesting subgraphs in attributed graph algorithm (MISAGA). MISAGA performs its tasks by first using a probabilistic measure to determine whether the strength of association between a pair of attribute values is strong enough to be interesting. Given the interesting pairs of attribute values, then the degree of association is computed for each pair of vertices using an information theoretic measure. Based on the edge structure and degree of association between each pair of vertices, MISAGA identifies interesting subgraphs by formulating it as a constrained optimization problem and solves it by identifying the optimal affiliation of subgraphs for the vertices in the attributed graph. MISAGA has been tested with several large-sized real graphs and is found to be potentially very useful for various applications.

  20. Using graph approach for managing connectivity in integrative landscape modelling

    Science.gov (United States)

    Rabotin, Michael; Fabre, Jean-Christophe; Libres, Aline; Lagacherie, Philippe; Crevoisier, David; Moussa, Roger

    2013-04-01

    In cultivated landscapes, a lot of landscape elements such as field boundaries, ditches or banks strongly impact water flows, mass and energy fluxes. At the watershed scale, these impacts are strongly conditionned by the connectivity of these landscape elements. An accurate representation of these elements and of their complex spatial arrangements is therefore of great importance for modelling and predicting these impacts.We developped in the framework of the OpenFLUID platform (Software Environment for Modelling Fluxes in Landscapes) a digital landscape representation that takes into account the spatial variabilities and connectivities of diverse landscape elements through the application of the graph theory concepts. The proposed landscape representation consider spatial units connected together to represent the flux exchanges or any other information exchanges. Each spatial unit of the landscape is represented as a node of a graph and relations between units as graph connections. The connections are of two types - parent-child connection and up/downstream connection - which allows OpenFLUID to handle hierarchical graphs. Connections can also carry informations and graph evolution during simulation is possible (connections or elements modifications). This graph approach allows a better genericity on landscape representation, a management of complex connections and facilitate development of new landscape representation algorithms. Graph management is fully operational in OpenFLUID for developers or modelers ; and several graph tools are available such as graph traversal algorithms or graph displays. Graph representation can be managed i) manually by the user (for example in simple catchments) through XML-based files in easily editable and readable format or ii) by using methods of the OpenFLUID-landr library which is an OpenFLUID library relying on common open-source spatial libraries (ogr vector, geos topologic vector and gdal raster libraries). Open

  1. Practical graph mining with R

    CERN Document Server

    Hendrix, William; Jenkins, John; Padmanabhan, Kanchana; Chakraborty, Arpan

    2014-01-01

    Practical Graph Mining with R presents a "do-it-yourself" approach to extracting interesting patterns from graph data. It covers many basic and advanced techniques for the identification of anomalous or frequently recurring patterns in a graph, the discovery of groups or clusters of nodes that share common patterns of attributes and relationships, the extraction of patterns that distinguish one category of graphs from another, and the use of those patterns to predict the category of new graphs. Hands-On Application of Graph Data Mining Each chapter in the book focuses on a graph mining task, such as link analysis, cluster analysis, and classification. Through applications using real data sets, the book demonstrates how computational techniques can help solve real-world problems. The applications covered include network intrusion detection, tumor cell diagnostics, face recognition, predictive toxicology, mining metabolic and protein-protein interaction networks, and community detection in social networks. De...

  2. Canonical Labelling of Site Graphs

    Directory of Open Access Journals (Sweden)

    Nicolas Oury

    2013-06-01

    Full Text Available We investigate algorithms for canonical labelling of site graphs, i.e. graphs in which edges bind vertices on sites with locally unique names. We first show that the problem of canonical labelling of site graphs reduces to the problem of canonical labelling of graphs with edge colourings. We then present two canonical labelling algorithms based on edge enumeration, and a third based on an extension of Hopcroft's partition refinement algorithm. All run in quadratic worst case time individually. However, one of the edge enumeration algorithms runs in sub-quadratic time for graphs with "many" automorphisms, and the partition refinement algorithm runs in sub-quadratic time for graphs with "few" bisimulation equivalences. This suite of algorithms was chosen based on the expectation that graphs fall in one of those two categories. If that is the case, a combined algorithm runs in sub-quadratic worst case time. Whether this expectation is reasonable remains an interesting open problem.

  3. Connected Cubic Network Graph

    Directory of Open Access Journals (Sweden)

    Burhan Selçuk

    2017-06-01

    Full Text Available Hypercube is a popular interconnection network. Due to the popularity of hypercube, more researchers pay a great effort to develop the different variants of hypercube. In this paper, we have proposed a variant of hypercube which is called as “Connected Cubic Network Graphs”, and have investigated the Hamilton-like properties of Connected Cubic Network Graphs (CCNG. Firstly, we defined CCNG and showed the characteristic analyses of CCNG. Then, we showed that the CCNG has the properties of Hamilton graph, and can be labeled using a Gray coding based recursive algorithm. Finally, we gave the comparison results, a routing algorithm and a bitonic sort algorithm for CCNG. In case of sparsity and cost, CCNG is better than Hypercube.

  4. An Unusual Exponential Graph

    Science.gov (United States)

    Syed, M. Qasim; Lovatt, Ian

    2014-01-01

    This paper is an addition to the series of papers on the exponential function begun by Albert Bartlett. In particular, we ask how the graph of the exponential function y = e[superscript -t/t] would appear if y were plotted versus ln t rather than the normal practice of plotting ln y versus t. In answering this question, we find a new way to…

  5. Graphs in molecular biology

    Directory of Open Access Journals (Sweden)

    Falcon Seth

    2007-09-01

    Full Text Available Abstract Graph theoretical concepts are useful for the description and analysis of interactions and relationships in biological systems. We give a brief introduction into some of the concepts and their areas of application in molecular biology. We discuss software that is available through the Bioconductor project and present a simple example application to the integration of a protein-protein interaction and a co-expression network.

  6. Convex Graph Invariants

    Science.gov (United States)

    2010-12-02

    evaluating the function ΘP (A) for any fixed A,P is equivalent to solving the so-called Quadratic Assignment Problem ( QAP ), and thus we can employ various...tractable linear programming, spectral, and SDP relaxations of QAP [40, 11, 33]. In particular we discuss recent work [14] on exploiting group...symmetry in SDP relaxations of QAP , which is useful for approximately computing elementary convex graph invariants in many interesting cases. Finally in

  7. Factorized Graph Matching.

    Science.gov (United States)

    Zhou, Feng; de la Torre, Fernando

    2015-11-19

    Graph matching (GM) is a fundamental problem in computer science, and it plays a central role to solve correspondence problems in computer vision. GM problems that incorporate pairwise constraints can be formulated as a quadratic assignment problem (QAP). Although widely used, solving the correspondence problem through GM has two main limitations: (1) the QAP is NP-hard and difficult to approximate; (2) GM algorithms do not incorporate geometric constraints between nodes that are natural in computer vision problems. To address aforementioned problems, this paper proposes factorized graph matching (FGM). FGM factorizes the large pairwise affinity matrix into smaller matrices that encode the local structure of each graph and the pairwise affinity between edges. Four are the benefits that follow from this factorization: (1) There is no need to compute the costly (in space and time) pairwise affinity matrix; (2) The factorization allows the use of a path-following optimization algorithm, that leads to improved optimization strategies and matching performance; (3) Given the factorization, it becomes straight-forward to incorporate geometric transformations (rigid and non-rigid) to the GM problem. (4) Using a matrix formulation for the GM problem and the factorization, it is easy to reveal commonalities and differences between different GM methods. The factorization also provides a clean connection with other matching algorithms such as iterative closest point; Experimental results on synthetic and real databases illustrate how FGM outperforms state-of-the-art algorithms for GM. The code is available at http://humansensing.cs.cmu.edu/fgm.

  8. Graphs cospectral with a friendship graph or its complement

    Directory of Open Access Journals (Sweden)

    Alireza Abdollahi

    2013-12-01

    Full Text Available Let $n$ be any positive integer and let $F_n$ be the friendship (or Dutch windmill graph with $2n+1$ vertices and $3n$ edges. Here we study graphs with the same adjacency spectrum as the $F_n$. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let $G$ be a graph cospectral with $F_n$. Here we prove that if $G$ has no cycle of length $4$ or $5$, then $Gcong F_n$. Moreover if $G$ is connected and planar then $Gcong F_n$.All but one of connected components of $G$ are isomorphic to $K_2$.The complement $overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $overline{F_n}$ is cospectral with a graph $H$, then $Hcong overline{F_n}$.

  9. A graphical representation of equivalence classes of AMP chain graphs

    Czech Academy of Sciences Publication Activity Database

    Roverato, A.; Studený, Milan

    2006-01-01

    Roč. 7, č. 6 (2006), s. 1045-1078 ISSN 1532-4435 R&D Projects: GA ČR GA201/04/0393 Institutional research plan: CEZ:AV0Z10750506 Keywords : chain graph * AMP Markov equivalence * strong equivalence * largest deflagged graph Subject RIV: BA - General Mathematics Impact factor: 2.255, year: 2006 http://library.utia.cas.cz/separaty/historie/studeny-0040067.pdf

  10. X-Graphs: Language and Algorithms for Heterogeneous Graph Streams

    Science.gov (United States)

    2017-09-01

    parallel implementations for many key graph algorithms, conversions between tables and graphs and Python language bindings. SNAP is widely deployed...1. We have used Delite to develop a suite of DSLs for data analysis (query processing, machine learning , and graph processing). Approved for Public...range of users, interested in network analysis: support for Python - a major programming language for data scientists, documentation, tutorials, and

  11. Contact Graph Routing

    Science.gov (United States)

    Burleigh, Scott C.

    2011-01-01

    Contact Graph Routing (CGR) is a dynamic routing system that computes routes through a time-varying topology of scheduled communication contacts in a network based on the DTN (Delay-Tolerant Networking) architecture. It is designed to enable dynamic selection of data transmission routes in a space network based on DTN. This dynamic responsiveness in route computation should be significantly more effective and less expensive than static routing, increasing total data return while at the same time reducing mission operations cost and risk. The basic strategy of CGR is to take advantage of the fact that, since flight mission communication operations are planned in detail, the communication routes between any pair of bundle agents in a population of nodes that have all been informed of one another's plans can be inferred from those plans rather than discovered via dialogue (which is impractical over long one-way-light-time space links). Messages that convey this planning information are used to construct contact graphs (time-varying models of network connectivity) from which CGR automatically computes efficient routes for bundles. Automatic route selection increases the flexibility and resilience of the space network, simplifying cross-support and reducing mission management costs. Note that there are no routing tables in Contact Graph Routing. The best route for a bundle destined for a given node may routinely be different from the best route for a different bundle destined for the same node, depending on bundle priority, bundle expiration time, and changes in the current lengths of transmission queues for neighboring nodes; routes must be computed individually for each bundle, from the Bundle Protocol agent's current network connectivity model for the bundle s destination node (the contact graph). Clearly this places a premium on optimizing the implementation of the route computation algorithm. The scalability of CGR to very large networks remains a research topic

  12. Graphs Theory and Applications

    CERN Document Server

    Fournier, Jean-Claude

    2008-01-01

    This book provides a pedagogical and comprehensive introduction to graph theory and its applications. It contains all the standard basic material and develops significant topics and applications, such as: colorings and the timetabling problem, matchings and the optimal assignment problem, and Hamiltonian cycles and the traveling salesman problem, to name but a few. Exercises at various levels are given at the end of each chapter, and a final chapter presents a few general problems with hints for solutions, thus providing the reader with the opportunity to test and refine their knowledge on the

  13. Nested Dynamic Condition Response Graphs

    DEFF Research Database (Denmark)

    Hildebrandt, Thomas; Mukkamala, Raghava Rao; Slaats, Tijs

    2012-01-01

    We present an extension of the recently introduced declarative process model Dynamic Condition Response Graphs ( DCR Graphs) to allow nested subgraphs and a new milestone relation between events. The extension was developed during a case study carried out jointly with our industrial partner...... Exformatics, a danish provider of case and workflow management systems. We formalize the semantics by giving first a map from Nested to (flat) DCR Graphs with milestones, and then extending the previously given mapping from DCR Graphs to Buchi-automata to include the milestone relation....

  14. Spectral partitioning in equitable graphs.

    Science.gov (United States)

    Barucca, Paolo

    2017-06-01

    Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e., random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKay's law for random regular graphs is found analytically to apply also for modular and bipartite structures when blocks are homogeneous. An exact solution to graph partitioning for two equal-sized communities is proposed and verified numerically, and a conjecture on the absence of an efficient recovery detectability transition in equitable graphs is suggested. A final discussion summarizes results and outlines their relevance for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits in stochastic block models.

  15. Multi-Level Anomaly Detection on Time-Varying Graph Data

    Energy Technology Data Exchange (ETDEWEB)

    Bridges, Robert A [ORNL; Collins, John P [ORNL; Ferragut, Erik M [ORNL; Laska, Jason A [ORNL; Sullivan, Blair D [ORNL

    2015-01-01

    This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labelled, streaming graph data. We introduce a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. Specifically, probability models describing coarse subgraphs are built by aggregating probabilities at finer levels, and these closely related hierarchical models simultaneously detect deviations from expectation. This technique provides insight into a graph's structure and internal context that may shed light on a detected event. Additionally, this multi-scale analysis facilitates intuitive visualizations by allowing users to narrow focus from an anomalous graph to particular subgraphs or nodes causing the anomaly. For evaluation, two hierarchical anomaly detectors are tested against a baseline Gaussian method on a series of sampled graphs. We demonstrate that our graph statistics-based approach outperforms both a distribution-based detector and the baseline in a labeled setting with community structure, and it accurately detects anomalies in synthetic and real-world datasets at the node, subgraph, and graph levels. To illustrate the accessibility of information made possible via this technique, the anomaly detector and an associated interactive visualization tool are tested on NCAA football data, where teams and conferences that moved within the league are identified with perfect recall, and precision greater than 0.786.

  16. Quantum Graph Analysis

    Energy Technology Data Exchange (ETDEWEB)

    Maunz, Peter Lukas Wilhelm [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Sterk, Jonathan David [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Lobser, Daniel [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Parekh, Ojas D. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Ryan-Anderson, Ciaran [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States)

    2016-01-01

    In recent years, advanced network analytics have become increasingly important to na- tional security with applications ranging from cyber security to detection and disruption of ter- rorist networks. While classical computing solutions have received considerable investment, the development of quantum algorithms to address problems, such as data mining of attributed relational graphs, is a largely unexplored space. Recent theoretical work has shown that quan- tum algorithms for graph analysis can be more efficient than their classical counterparts. Here, we have implemented a trapped-ion-based two-qubit quantum information proces- sor to address these goals. Building on Sandia's microfabricated silicon surface ion traps, we have designed, realized and characterized a quantum information processor using the hyperfine qubits encoded in two 171 Yb + ions. We have implemented single qubit gates using resonant microwave radiation and have employed Gate set tomography (GST) to characterize the quan- tum process. For the first time, we were able to prove that the quantum process surpasses the fault tolerance thresholds of some quantum codes by demonstrating a diamond norm distance of less than 1 . 9 x 10 [?] 4 . We used Raman transitions in order to manipulate the trapped ions' motion and realize two-qubit gates. We characterized the implemented motion sensitive and insensitive single qubit processes and achieved a maximal process infidelity of 6 . 5 x 10 [?] 5 . We implemented the two-qubit gate proposed by Molmer and Sorensen and achieved a fidelity of more than 97 . 7%.

  17. ILIGRA : An Efficient Inverse Line Graph Algorithm

    NARCIS (Netherlands)

    Liu, D.; Trajanovski, S.; Van Mieghem, P.

    2014-01-01

    This paper presents a new and efficient algorithm, ILIGRA, for inverse line graph construction. Given a line graph H, ILIGRA constructs its root graph G with the time complexity being linear in the number of nodes in H. If ILIGRA does not know whether the given graph H is a line graph, it firstly

  18. On Graph Rewriting, Reduction and Evaluation

    DEFF Research Database (Denmark)

    Zerny, Ian

    2010-01-01

    We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.'s mechanical program derivations from the world of terms to the world of graphs. We also outline how to inter......-derive a third style of graph reduction: a graph evaluator....

  19. Using Graph Transformations and Graph Abstractions for Software Verification

    NARCIS (Netherlands)

    Zambon, Eduardo; Ehrig, Hartmut; Rensink, Arend; Rozenberg, Grzegorz; Schurr, Andy

    In this abstract we present an overview of our intended approach for the verification of software written in imperative programming languages. This approach is based on model checking of graph transition systems (GTS), where each program state is modeled as a graph and the exploration engine is

  20. Kirchhoff index of graphs and some graph operations

    Indian Academy of Sciences (India)

    We define the -repetition of to be the graph obtained by joining y i to x j for each i ∈ V ( T ) and each child of . In this paper, we compute the Kirchhoff index of the -repetition of in terms of parameters of and . Also we study how K f ( G ) behaves under some graph operations such as joining vertices or ...

  1. Dynamic graphs, community detection, and Riemannian geometry

    Energy Technology Data Exchange (ETDEWEB)

    Bakker, Craig; Halappanavar, Mahantesh; Visweswara Sathanur, Arun

    2018-03-29

    A community is a subset of a wider network where the members of that subset are more strongly connected to each other than they are to the rest of the network. In this paper, we consider the problem of identifying and tracking communities in graphs that change over time {dynamic community detection} and present a framework based on Riemannian geometry to aid in this task. Our framework currently supports several important operations such as interpolating between and averaging over graph snapshots. We compare these Riemannian methods with entry-wise linear interpolation and that the Riemannian methods are generally better suited to dynamic community detection. Next steps with the Riemannian framework include developing higher-order interpolation methods (e.g. the analogues of polynomial and spline interpolation) and a Riemannian least-squares regression method for working with noisy data.

  2. Total Domination Versus Paired-Domination in Regular Graphs

    Directory of Open Access Journals (Sweden)

    Cyman Joanna

    2018-05-01

    Full Text Available A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G, is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G, and the paired-domination number, γpr(G, respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012 435–447] that γpr(G/γt(G ≤ (2k/(k+1. In the special case when k = 2, we observe that γpr(G/γt(G ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G/γt(G ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G/γt(G = (2k/(k + 1, then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G/γt(G ≤ (2k/(k +1, with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.

  3. Graph Theory. 2. Vertex Descriptors and Graph Coloring

    Directory of Open Access Journals (Sweden)

    Lorentz JÄNTSCHI

    2002-12-01

    Full Text Available This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.

  4. Multi-channel coherent perfect absorbers

    KAUST Repository

    Bai, Ping

    2016-05-18

    The absorption efficiency of a coherent perfect absorber usually depends on the phase coherence of the incident waves on the surfaces. Here, we present a scheme to create a multi-channel coherent perfect absorber in which the constraint of phase coherence is loosened. The scheme has a multi-layer structure such that incident waves in different channels with different angular momenta can be simultaneously and perfectly absorbed. This absorber is robust in achieving high absorption efficiency even if the incident waves become "incoherent" and possess "random" wave fronts. Our work demonstrates a unique approach to designing highly efficient metamaterial absorbers. © CopyrightEPLA, 2016.

  5. Chordal Graphs and Semidefinite Optimization

    DEFF Research Database (Denmark)

    Vandenberghe, Lieven; Andersen, Martin Skovgaard

    2015-01-01

    Chordal graphs play a central role in techniques for exploiting sparsity in large semidefinite optimization problems and in related con-vex optimization problems involving sparse positive semidefinite matrices. Chordal graph properties are also fundamental to several classical results in combinat...

  6. DYNAMICALLY MAINTAINING THE VISIBILITY GRAPH

    NARCIS (Netherlands)

    VEGTER, G

    1991-01-01

    An algorithm is presented to maintain the visibility graph of a set of N line segments in the plane in O(log2 N + K log N) time, where K is the total number of arcs of the visibility graph that are destroyed or created upon insertion or deletion of a line segment. The line segments should be

  7. A cluster algorithm for graphs

    NARCIS (Netherlands)

    S. van Dongen

    2000-01-01

    textabstractA cluster algorithm for graphs called the emph{Markov Cluster algorithm (MCL~algorithm) is introduced. The algorithm provides basically an interface to an algebraic process defined on stochastic matrices, called the MCL~process. The graphs may be both weighted (with nonnegative weight)

  8. The planar cubic Cayley graphs

    CERN Document Server

    Georgakopoulos, Agelos

    2018-01-01

    The author obtains a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of them. This turns out to be a rich class, comprising several infinite families. He obtains counterexamples to conjectures of Mohar, Bonnington and Watkins. The author's analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.

  9. The planar cubic cayley graphs

    CERN Document Server

    Georgakopoulos, Agelos

    2018-01-01

    The author obtains a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of them. This turns out to be a rich class, comprising several infinite families. He obtains counterexamples to conjectures of Mohar, Bonnington and Watkins. The author's analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.

  10. Word graphs: The second set

    NARCIS (Netherlands)

    Hoede, C.; Liu, X

    1998-01-01

    In continuation of the paper of Hoede and Li on word graphs for a set of prepositions, word graphs are given for adjectives, adverbs and Chinese classifier words. It is argued that these three classes of words belong to a general class of words that may be called adwords. These words express the

  11. Tools for Large Graph Mining

    Science.gov (United States)

    2005-06-01

    relationship, trust, etc.) between people. • User Psychology : Clickstream graphs are bipartite graphs connecting Internet users to the websites they visit...document groups (say, science fiction novels and thrillers ), based on the word groups that occur most frequently in them. A user who prefers one

  12. Bell inequalities for graph states

    International Nuclear Information System (INIS)

    Toth, G.; Hyllus, P.; Briegel, H.J.; Guehne, O.

    2005-01-01

    Full text: In the last years graph states have attracted an increasing interest in the field of quantum information theory. Graph states form a family of multi-qubit states which comprises many popular states such as the GHZ states and the cluster states. They also play an important role in applications. For instance, measurement based quantum computation uses graph states as resources. From a theoretical point of view, it is remarkable that graph states allow for a simple description in terms of stabilizing operators. In this contribution, we investigate the non-local properties of graph states. We derive a family of Bell inequalities which require three measurement settings for each party and are maximally violated by graph states. In turn, any graph state violates at least one of the inequalities. We show that for certain types of graph states the violation of these inequalities increases exponentially with the number of qubits. We also discuss connections to other entanglement properties such as the positively of the partial transpose or the geometric measure of entanglement. (author)

  13. Submanifolds weakly associated with graphs

    Indian Academy of Sciences (India)

    theory by defining submanifolds weakly associated with graphs. We prove that, in a local sense, every submanifold satisfies such an association, and other general results. Finally, we study submanifolds associated with graphs either in low dimensions or belonging to some special families. Keywords. Almost Hermitian ...

  14. A Collection of Features for Semantic Graphs

    Energy Technology Data Exchange (ETDEWEB)

    Eliassi-Rad, T; Fodor, I K; Gallagher, B

    2007-05-02

    Semantic graphs are commonly used to represent data from one or more data sources. Such graphs extend traditional graphs by imposing types on both nodes and links. This type information defines permissible links among specified nodes and can be represented as a graph commonly referred to as an ontology or schema graph. Figure 1 depicts an ontology graph for data from National Association of Securities Dealers. Each node type and link type may also have a list of attributes. To capture the increased complexity of semantic graphs, concepts derived for standard graphs have to be extended. This document explains briefly features commonly used to characterize graphs, and their extensions to semantic graphs. This document is divided into two sections. Section 2 contains the feature descriptions for static graphs. Section 3 extends the features for semantic graphs that vary over time.

  15. Semi-Markov graph dynamics.

    Directory of Open Access Journals (Sweden)

    Marco Raberto

    Full Text Available In this paper, we outline a model of graph (or network dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections with algebraic geometry are briefly discussed. Moreover, for the sake of simplicity, we focus on the space of undirected graphs with a fixed number of nodes. However, in an example, we present an interbank market model where it is meaningful to use directed graphs or even weighted graphs.

  16. RJSplot: Interactive Graphs with R.

    Science.gov (United States)

    Barrios, David; Prieto, Carlos

    2018-03-01

    Data visualization techniques provide new methods for the generation of interactive graphs. These graphs allow a better exploration and interpretation of data but their creation requires advanced knowledge of graphical libraries. Recent packages have enabled the integration of interactive graphs in R. However, R provides limited graphical packages that allow the generation of interactive graphs for computational biology applications. The present project has joined the analytical power of R with the interactive graphical features of JavaScript in a new R package (RJSplot). It enables the easy generation of interactive graphs in R, provides new visualization capabilities, and contributes to the advance of computational biology analytical methods. At present, 16 interactive graphics are available in RJSplot, such as the genome viewer, Manhattan plots, 3D plots, heatmaps, dendrograms, networks, and so on. The RJSplot package is freely available online at http://rjsplot.net. © 2018 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim.

  17. Quantum chaos on discrete graphs

    Energy Technology Data Exchange (ETDEWEB)

    Smilansky, Uzy [Department of Physics of Complex Systems, Weizmann Institute of Science, Rehovot 76100 (Israel); Isaac Newton Institute for Mathematical Sciences, 20 Clarkson Road, Cambridge CB3 0EH (United Kingdom)

    2007-07-06

    Adapting a method developed for the study of quantum chaos on quantum (metric) graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76), spectral {zeta} functions and trace formulae for discrete Laplacians on graphs are derived. This is achieved by expressing the spectral secular equation in terms of the periodic orbits of the graph and obtaining functions which belong to the class of {zeta} functions proposed originally by Ihara (1966 J. Mat. Soc. Japan 18 219) and expanded by subsequent authors (Stark and Terras 1996 Adv. Math. 121 124, Kotani and Sunada 2000 J. Math. Sci. Univ. Tokyo 7 7). Finally, a model of 'classical dynamics' on the discrete graph is proposed. It is analogous to the corresponding classical dynamics derived for quantum graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76). (fast track communication)

  18. On the Extension Complexity of Stable Set Polytopes for Perfect Graphs

    NARCIS (Netherlands)

    H. Hu (Hao)

    2015-01-01

    htmlabstractIn linear programming one can formulate many combinatorial optimization problems as optimizing a linear function over a feasible region that is a polytope. Given a polytope P, any non-redundant description of P contains precisely one inequality for each facet. A polytope

  19. Isolate domination in graphs

    Directory of Open Access Journals (Sweden)

    I. Sahul Hamid

    2016-07-01

    Full Text Available A set D of vertices of a graph G is called a dominating set of G if every vertex in V(G−D is adjacent to a vertex in D. A dominating set S such that the subgraph 〈S〉 induced by S has at least one isolated vertex is called an isolate dominating set. An isolate dominating set none of whose proper subset is an isolate dominating set is a minimal isolate dominating set. The minimum and maximum cardinality of a minimal isolate dominating set are called the isolate domination number γ0 and the upper isolate domination number Γ0 respectively. In this paper we initiate a study on these parameters.

  20. Environmental evolutionary graph theory.

    Science.gov (United States)

    Maciejewski, Wes; Puleo, Gregory J

    2014-11-07

    Understanding the influence of an environment on the evolution of its resident population is a major challenge in evolutionary biology. Great progress has been made in homogeneous population structures while heterogeneous structures have received relatively less attention. Here we present a structured population model where different individuals are best suited to different regions of their environment. The underlying structure is a graph: individuals occupy vertices, which are connected by edges. If an individual is suited for their vertex, they receive an increase in fecundity. This framework allows attention to be restricted to the spatial arrangement of suitable habitat. We prove some basic properties of this model and find some counter-intuitive results. Notably, (1) the arrangement of suitable sites is as important as their proportion, and (2) decreasing the proportion of suitable sites may result in a decrease in the fixation time of an allele. Copyright © 2014 Elsevier Ltd. All rights reserved.

  1. On characterizing terrain visibility graphs

    Directory of Open Access Journals (Sweden)

    William Evans

    2015-06-01

    Full Text Available A terrain is an $x$-monotone polygonal line in the $xy$-plane. Two vertices of a terrain are mutually visible if and only if there is no terrain vertex on or above the open line segment connecting them. A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. We would like to find properties that are both necessary and sufficient for a graph to be a terrain visibility graph; that is, we would like to characterize terrain visibility graphs.Abello et al. [Discrete and Computational Geometry, 14(3:331--358, 1995] showed that all terrain visibility graphs are “persistent”. They showed that the visibility information of a terrain point set implies some ordering requirements on the slopes of the lines connecting pairs of points in any realization, and as a step towards showing sufficiency, they proved that for any persistent graph $M$ there is a total order on the slopes of the (pseudo lines in a generalized configuration of points whose visibility graph is $M$.We give a much simpler proof of this result by establishing an orientation to every triple of vertices, reflecting some slope ordering requirements that are consistent with $M$ being the visibility graph, and prove that these requirements form a partial order. We give a faster algorithm to construct a total order on the slopes. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid that we show is a restricted type of $3$-signotope.

  2. Plasmonic titanium nitride nanostructures for perfect absorbers

    DEFF Research Database (Denmark)

    Guler, Urcan; Li, Wen-Wei; Kinsey, Nathaniel

    2013-01-01

    We propose a metamaterial based perfect absorber in the visible region, and investigate the performance of titanium nitride as an alternative plasmonic material. Numerical and experimental results reveal that titanium nitride performs better than gold as a plasmonic absorbing material...

  3. Optically Modulated Multiband Terahertz Perfect Absorber

    DEFF Research Database (Denmark)

    Seren, Huseyin R.; Keiser, George R.; Cao, Lingyue

    2014-01-01

    response of resonant metamaterials continues to be a challengingendeavor. Resonant perfect absorbers have flourished as one of the mostpromising metamaterial devices with applications ranging from power har-vesting to terahertz imaging. Here, an optically modulated resonant perfectabsorber is presented...

  4. Graph embedding with rich information through heterogeneous graph

    KAUST Repository

    Sun, Guolei

    2017-11-12

    Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most existing algorithms for graph embedding only rely on the topology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this thesis, we proposed a novel and general framework for graph embedding with rich text information (GERI) through constructing a heterogeneous network, in which we integrate node and edge content information with graph topology. Specially, we designed a novel biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. Our sampling strategy can compromise between BFS and DFS local search on heterogeneous graph. To further improve our algorithm, we proposed semi-supervised GERI (SGERI), which learns graph embedding in an discriminative manner through heterogeneous network with label information. The efficacy of our method is demonstrated by extensive comparison experiments with 9 baselines over multi-label and multi-class classification on various datasets including Citeseer, Cora, DBLP and Wiki. It shows that GERI improves the Micro-F1 and Macro-F1 of node classification up to 10%, and SGERI improves GERI by 5% in Wiki.

  5. Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms

    Directory of Open Access Journals (Sweden)

    Furmańczyk Hanna

    2016-09-01

    Full Text Available In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.

  6. On some properties of doughnut graphs

    Directory of Open Access Journals (Sweden)

    Md. Rezaul Karim

    2016-08-01

    Full Text Available The class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties.

  7. Completeness and regularity of generalized fuzzy graphs.

    Science.gov (United States)

    Samanta, Sovan; Sarkar, Biswajit; Shin, Dongmin; Pal, Madhumangal

    2016-01-01

    Fuzzy graphs are the backbone of many real systems like networks, image, scheduling, etc. But, due to some restriction on edges, fuzzy graphs are limited to represent for some systems. Generalized fuzzy graphs are appropriate to avoid such restrictions. In this study generalized fuzzy graphs are introduced. In this study, matrix representation of generalized fuzzy graphs is described. Completeness and regularity are two important parameters of graph theory. Here, regular and complete generalized fuzzy graphs are introduced. Some properties of them are discussed. After that, effective regular graphs are exemplified.

  8. Comparison and Enumeration of Chemical Graphs

    Science.gov (United States)

    Akutsu, Tatsuya; Nagamochi, Hiroshi

    2013-01-01

    Chemical compounds are usually represented as graph structured data in computers. In this review article, we overview several graph classes relevant to chemical compounds and the computational complexities of several fundamental problems for these graph classes. In particular, we consider the following problems: determining whether two chemical graphs are identical, determining whether one input chemical graph is a part of the other input chemical graph, finding a maximum common part of two input graphs, finding a reaction atom mapping, enumerating possible chemical graphs, and enumerating stereoisomers. We also discuss the relationship between the fifth problem and kernel functions for chemical compounds. PMID:24688697

  9. Colored graphs and matrix integrals

    International Nuclear Information System (INIS)

    Artamkin, I.V.

    2007-12-01

    In this article we discuss two different asymptotic expansions of matrix integrals. The original approach using the so-called Feynman diagram techniques leads to sums over isomorphism classes of ribbon graphs. Asymptotic expansions of more general Gaussian integrals are sums over isomorphism classes of colored graphs without ribbon structure. Here we derive the former expansion from the latter one. This provides an independent proof for the expansion used by Kontsevich. It might be very interesting to compare the algebra arising in these two approaches. The asymptotic expansion using ribbon graphs leads to the tau function of the KDV hierarchy while the sums over colored graphs satisfy simple partial differential equations which generalize the Burgers equation. We describe the general approach using colored graphs in the second section. In the third section we specialize the results of the second section for the matrix integral. In this section we also derive the expansion over ribbon graphs. The proof is based on simple topological considerations which are contained in section 5. In the last section we give an explicit calculation of the first term of the expansion using colored graphs

  10. Hierarchy of modular graph identities

    Energy Technology Data Exchange (ETDEWEB)

    D’Hoker, Eric; Kaidi, Justin [Mani L. Bhaumik Institute for Theoretical Physics, Department of Physics and Astronomy,University of California,Los Angeles, CA 90095 (United States)

    2016-11-09

    The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.

  11. Identifying vertex covers in graphs

    DEFF Research Database (Denmark)

    Henning, Michael A.; Yeo, Anders

    2012-01-01

    An identifying vertex cover in a graph G is a subset T of vertices in G that has a nonempty intersection with every edge of G such that T distinguishes the edges, that is, e∩T ≠ 0 for every edge e in G and e∩T ≠ f∩T for every two distinct edges e and f in G. The identifying vertex cover number TD......(G) of G is the minimum size of an identifying vertex cover in G. We observe that TD(G)+ρ(G) = |V (G)|, where ρ(G) denotes the packing number of G. We conjecture that if G is a graph of order n and size m with maximum degree Δ, then TD(G) ≤(Δ(Δ-1)/ Δ2+1)n + (2/Δ2+1) m. If the conjecture is true......, then the bound is best possible for all Δ ≥ 1. We prove this conjecture when Δ ≥ 1 and G is a Δ-regular graph. The three known Moore graphs of diameter 2, namely the 5-cycle, the Petersen graph and the Hoffman-Singleton graph, are examples of regular graphs that achieves equality in the upper bound. We also...

  12. A lossy graph model for delay reduction in generalized instantly decodable network coding

    KAUST Repository

    Douik, Ahmed S.

    2014-06-01

    The problem of minimizing the decoding delay in Generalized instantly decodable network coding (G-IDNC) for both perfect and lossy feedback scenarios is formulated as a maximum weight clique problem over the G-IDNC graph in. In this letter, we introduce a new lossy G-IDNC graph (LG-IDNC) model to further minimize the decoding delay in lossy feedback scenarios. Whereas the G-IDNC graph represents only doubtless combinable packets, the LG-IDNC graph represents also uncertain packet combinations, arising from lossy feedback events, when the expected decoding delay of XORing them among themselves or with other certain packets is lower than that expected when sending these packets separately. We compare the decoding delay performance of LG-IDNC and G-IDNC graphs through extensive simulations. Numerical results show that our new LG-IDNC graph formulation outperforms the G-IDNC graph formulation in all lossy feedback situations and achieves significant improvement in the decoding delay especially when the feedback erasure probability is higher than the packet erasure probability. © 2012 IEEE.

  13. XML Graphs in Program Analysis

    DEFF Research Database (Denmark)

    Møller, Anders; Schwartzbach, Michael I.

    2011-01-01

    XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation...... of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey the use of XML graphs for program analysis with four very different languages: XACT (XML in Java), Java Servlets (Web application programming), XSugar...... (transformations between XML and non-XML data), and XSLT (stylesheets for transforming XML documents)....

  14. Large networks and graph limits

    CERN Document Server

    Lovász, László

    2012-01-01

    Recently, it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks. Developing a mathematical theory of very large networks is an important challenge. This book describes one recent approach to this theory, the limit theory of graphs, which has emerged over the last decade. The theory has rich connections with other approaches to the study of large networks, such as "property testing" in computer science and regularity partition in graph theory. It has several applications in extremal graph theory, including the exact for

  15. Kirchhoff index of graphs and some graph operations

    Indian Academy of Sciences (India)

    Abstract. Let T be a rooted tree, G a connected graph, x,y ∈ V(G) be fixed and Gi's be |V(T )| disjoint copies of G with xi and yi denoting the corresponding copies of x and y in Gi, respectively. We define the T -repetition of G to be the graph obtained by joining yi to xj for each i ∈ V(T ) and each child j of i. In this paper, we ...

  16. Bounds for percolation thresholds on directed and undirected graphs

    Science.gov (United States)

    Hamilton, Kathleen; Pryadko, Leonid

    2015-03-01

    Percolation theory is an efficient approach to problems with strong disorder, e.g., in quantum or classical transport, composite materials, and diluted magnets. Recently, the growing role of big data in scientific and industrial applications has led to a renewed interest in graph theory as a tool for describing complex connections in various kinds of networks: social, biological, technological, etc. In particular, percolation on graphs has been used to describe internet stability, spread of contagious diseases and computer viruses; related models describe market crashes and viral spread in social networks. We consider site-dependent percolation on directed and undirected graphs, and present several exact bounds for location of the percolation transition in terms of the eigenvalues of matrices associated with graphs, including the adjacency matrix and the Hashimoto matrix used to enumerate non-backtracking walks. These bounds correspond t0 a mean field approximation and become asymptotically exact for graphs with no short cycles. We illustrate this convergence numerically by simulating percolation on several families of graphs with different cycle lengths. This research was supported in part by the NSF Grant PHY-1416578 and by the ARO Grant W911NF-11-1-0027.

  17. Minimum-weight perfect matching for non-intrinsic distances on the line

    OpenAIRE

    Delon, Julie; Salomon, Julien; Sobolevski, Andrei

    2011-01-01

    13 pages, figures in TiKZ, uses xcolor package; introduction and the concluding section have been expanded.; Consider a real line equipped with a (not necessarily intrinsic) distance. We deal with the minimum-weight perfect matching problem for a complete graph whose points are located on the line and whose edges have weights equal to distances along the line. This problem is closely related to one-dimensional Monge-Kantorovich trasnport optimization. The main result of the present note is a ...

  18. Towards Perfect Water Line Intensities

    Science.gov (United States)

    Lodi, L.; Tennyson, J.

    2012-06-01

    Over the last ten years the increased availability of computational resources and the steady refinement of theoretical methods have permitted more and more accurate first principle calculations of water-vapor spectra as exemplified, e.g., by the very successful BT2 line list both line positions and intensities, a reliable dipole moment surface (DMS), affecting line intensities. It is also very useful to several application to give reasonable uncertainty bars for computed quantities, an aspect which traditionally has received little attention. We report here recent progress leading to very accurate room-temperature linelists covering the range 0.05-20 000 cm-1, complete with uncertainty bars, for the H_218O and H_217O water isotopologues Line intensities were produced using a recent DMS produced by our group which is capable of giving line intensites accurate to 1% for most medium and strong transitions. Line positions are based if possible on the experimentally derived energy levels recently produced by a IUPAC task group and have a typical accuracy of 0.0002 cm-1; when experimentally derived energy levels are unavailable calculated line position are provided, with an accuracy of the order of 0.2 cm-1. An extension to the main isotopologue H_216O is currently underway. R. J. Barber, J. Tennyson, G. J. Harris and R. N. Tolchenov, Mon. Not. R. Astron. Soc. {368}, 1087-1094 (2006). L. Lodi and J. Tennyson, J. Quant. Spectrosc. Radiat. Trans. (2012), doi:10.1016/j.jqsrt.2012.02.023 L. Lodi, J. Tennyson and O. L. Polyansky, J. Chem. Phys. {135}, 034113 (2011). J. Tennyson at al., J. Quant. Spectrosc. Radiat. Trans. {110}, 573-96 (2009).

  19. Graph theory and combinatorial optimization

    CERN Document Server

    Marcotte, Odile; Avis, David

    2006-01-01

    A current treatment of cutting-edge topics in Graph Theory and Combinatorial Optimization by leading researchersIncludes heuristic advances and novel approaches to solving combinatorial optimization problems.

  20. Open Graphs and Computational Reasoning

    Directory of Open Access Journals (Sweden)

    Lucas Dixon

    2010-06-01

    Full Text Available We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information.

  1. Graph Model Based Indoor Tracking

    DEFF Research Database (Denmark)

    Jensen, Christian Søndergaard; Lu, Hua; Yang, Bin

    2009-01-01

    The tracking of the locations of moving objects in large indoor spaces is important, as it enables a range of applications related to, e.g., security and indoor navigation and guidance. This paper presents a graph model based approach to indoor tracking that offers a uniform data management...... infrastructure for different symbolic positioning technologies, e.g., Bluetooth and RFID. More specifically, the paper proposes a model of indoor space that comprises a base graph and mappings that represent the topology of indoor space at different levels. The resulting model can be used for one or several...... indoor positioning technologies. Focusing on RFID-based positioning, an RFID specific reader deployment graph model is built from the base graph model. This model is then used in several algorithms for constructing and refining trajectories from raw RFID readings. Empirical studies with implementations...

  2. Generating random networks and graphs

    CERN Document Server

    Coolen, Ton; Roberts, Ekaterina

    2017-01-01

    This book supports researchers who need to generate random networks, or who are interested in the theoretical study of random graphs. The coverage includes exponential random graphs (where the targeted probability of each network appearing in the ensemble is specified), growth algorithms (i.e. preferential attachment and the stub-joining configuration model), special constructions (e.g. geometric graphs and Watts Strogatz models) and graphs on structured spaces (e.g. multiplex networks). The presentation aims to be a complete starting point, including details of both theory and implementation, as well as discussions of the main strengths and weaknesses of each approach. It includes extensive references for readers wishing to go further. The material is carefully structured to be accessible to researchers from all disciplines while also containing rigorous mathematical analysis (largely based on the techniques of statistical mechanics) to support those wishing to further develop or implement the theory of rand...

  3. Submanifolds weakly associated with graphs

    Indian Academy of Sciences (India)

    Leuven: Katholieke Universiteit Leuven). (1990). [5] Etayo F, On quasi-slant submanifolds of an almost Hermitian manifold, Publ. Math. Debrecen 53 (1998) 217–223. [6] Harary F, Graph Theory (Reading: Addison-Wesley) (1972). [7] Papaghiuc N ...

  4. Graph anomalies in cyber communications

    Energy Technology Data Exchange (ETDEWEB)

    Vander Wiel, Scott A [Los Alamos National Laboratory; Storlie, Curtis B [Los Alamos National Laboratory; Sandine, Gary [Los Alamos National Laboratory; Hagberg, Aric A [Los Alamos National Laboratory; Fisk, Michael [Los Alamos National Laboratory

    2011-01-11

    Enterprises monitor cyber traffic for viruses, intruders and stolen information. Detection methods look for known signatures of malicious traffic or search for anomalies with respect to a nominal reference model. Traditional anomaly detection focuses on aggregate traffic at central nodes or on user-level monitoring. More recently, however, traffic is being viewed more holistically as a dynamic communication graph. Attention to the graph nature of the traffic has expanded the types of anomalies that are being sought. We give an overview of several cyber data streams collected at Los Alamos National Laboratory and discuss current work in modeling the graph dynamics of traffic over the network. We consider global properties and local properties within the communication graph. A method for monitoring relative entropy on multiple correlated properties is discussed in detail.

  5. A contribution to queens graphs

    DEFF Research Database (Denmark)

    Barat, Janos

    A graph $G$ is a queens graph if the vertices of $G$ can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position. We prove a conjecture of Beineke, Broere...... and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. % is not representable in the same way. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem. We also prove...... constructively that any finite subgraph of the grid or the hexagonal grid is a queens graph....

  6. SOUR graphs for efficient completion

    OpenAIRE

    Lynch, Christopher; Strogova, Polina

    1998-01-01

    International audience; We introduce a data structure called \\emphSOUR graphs and present an efficient Knuth-Bendix completion procedure based on it. \\emphSOUR graphs allow for a maximal structure sharing of terms in rewriting systems. The term representation is a dag representation, except that edges are labelled with equational constraints and variable renamings. The rewrite rules correspond to rewrite edges, the unification problems to unification edges. The Critical Pair and Simplificatio...

  7. Rectilinear Graphs and Angular Resolution

    NARCIS (Netherlands)

    Bodlaender, H.L.; Tel, G.

    2003-01-01

    In this note we show that a planar graph with angular resolution at least π/2 can be drawn with all angles an integer multiple of π/2, that is, in a rectilinear manner. Moreover, we show that for d ≠ 4, d › 2, having an angular resolution of 2π/d does not imply that the graph can be drawn with all

  8. Graph theory and its applications

    CERN Document Server

    Gross, Jonathan L

    2006-01-01

    Gross and Yellen take a comprehensive approach to graph theory that integrates careful exposition of classical developments with emerging methods, models, and practical needs. Their unparalleled treatment provides a text ideal for a two-semester course and a variety of one-semester classes, from an introductory one-semester course to courses slanted toward classical graph theory, operations research, data structures and algorithms, or algebra and topology.

  9. On dominator colorings in graphs

    Indian Academy of Sciences (India)

    A dominator coloring of a graph G is a proper coloring of G in which every vertex dominates every vertex of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by χd(G). In this paper we present several results on graphs ...

  10. a generalization of total graphs

    Indian Academy of Sciences (India)

    8

    Abstract. Let R be a commutative ring with nonzero identity, Ln(R) be the set of all lower triangular n × n matrices, and U be a triangular subset of. Rn i.e. the product of any lower triangular matrix with the transpose of any element of U, belongs to U. The graph GTn. U (Rn) is a simple graph whose ver- tices consists of all ...

  11. Port-Hamiltonian Systems on Open Graphs

    NARCIS (Netherlands)

    Schaft, A.J. van der; Maschke, B.M.

    2010-01-01

    In this talk we discuss how to define in an intrinsic manner port-Hamiltonian dynamics on open graphs. Open graphs are graphs where some of the vertices are boundary vertices (terminals), which allow interconnection with other systems. We show that a directed graph carries two natural Dirac

  12. A Modal-Logic Based Graph Abstraction

    NARCIS (Netherlands)

    Bauer, J.; Boneva, I.B.; Kurban, M.E.; Rensink, Arend; Ehrig, H; Heckel, R.; Rozenberg, G.; Taentzer, G.

    2008-01-01

    Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract

  13. Summary 2: Graph Grammar Verification through Abstraction

    NARCIS (Netherlands)

    Baldan, P.; Koenig, B.; Rensink, A.; Rensink, Arend; König, B.; Montanari, U.; Gardner, P.

    2005-01-01

    Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph grammars. This paper compares two existing approaches, based on abstractions of graph transformation systems. While in the unfolding approach graph grammars are

  14. On Graph Rewriting, Reduction and Evaluation

    DEFF Research Database (Denmark)

    Zerny, Ian

    2009-01-01

    We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt. To this end, we adapt Danvy et al.'s mechanical program derivations from the world of terms to the world of graphs. We also inter-derive a graph evaluator....

  15. Graphs with branchwidth at most three

    NARCIS (Netherlands)

    Bodlaender, H.L.; Thilikos, D.M.

    1997-01-01

    In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph

  16. A faithful functor among algebras and graphs

    OpenAIRE

    Falcón Ganfornina, Óscar Jesús; Falcón Ganfornina, Raúl Manuel; Núñez Valdés, Juan; Pacheco Martínez, Ana María; Villar Liñán, María Trinidad; Vigo Aguiar, Jesús (Coordinador)

    2016-01-01

    The problem of identifying a functor between the categories of algebras and graphs is currently open. Based on a known algorithm that identifies isomorphisms of Latin squares with isomorphism of vertex-colored graphs, we describe here a pair of graphs that enable us to find a faithful functor between finite-dimensional algebras over finite fields and these graphs.

  17. Constructing Dense Graphs with Unique Hamiltonian Cycles

    Science.gov (United States)

    Lynch, Mark A. M.

    2012-01-01

    It is not difficult to construct dense graphs containing Hamiltonian cycles, but it is difficult to generate dense graphs that are guaranteed to contain a unique Hamiltonian cycle. This article presents an algorithm for generating arbitrarily large simple graphs containing "unique" Hamiltonian cycles. These graphs can be turned into dense graphs…

  18. Hard graphs for the maximum clique problem

    NARCIS (Netherlands)

    Hoede, C.

    1988-01-01

    The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number.

  19. Dynamic Programming on Nominal Graphs

    Directory of Open Access Journals (Sweden)

    Nicklas Hoch

    2015-04-01

    Full Text Available Many optimization problems can be naturally represented as (hyper graphs, where vertices correspond to variables and edges to tasks, whose cost depends on the values of the adjacent variables. Capitalizing on the structure of the graph, suitable dynamic programming strategies can select certain orders of evaluation of the variables which guarantee to reach both an optimal solution and a minimal size of the tables computed in the optimization process. In this paper we introduce a simple algebraic specification with parallel composition and restriction whose terms up to structural axioms are the graphs mentioned above. In addition, free (unrestricted vertices are labelled with variables, and the specification includes operations of name permutation with finite support. We show a correspondence between the well-known tree decompositions of graphs and our terms. If an axiom of scope extension is dropped, several (hierarchical terms actually correspond to the same graph. A suitable graphical structure can be found, corresponding to every hierarchical term. Evaluating such a graphical structure in some target algebra yields a dynamic programming strategy. If the target algebra satisfies the scope extension axiom, then the result does not depend on the particular structure, but only on the original graph. We apply our approach to the parking optimization problem developed in the ASCENS e-mobility case study, in collaboration with Volkswagen. Dynamic programming evaluations are particularly interesting for autonomic systems, where actual behavior often consists of propagating local knowledge to obtain global knowledge and getting it back for local decisions.

  20. Chromatic polynomials of random graphs

    International Nuclear Information System (INIS)

    Van Bussel, Frank; Fliegner, Denny; Timme, Marc; Ehrlich, Christoph; Stolzenberg, Sebastian

    2010-01-01

    Chromatic polynomials and related graph invariants are central objects in both graph theory and statistical physics. Computational difficulties, however, have so far restricted studies of such polynomials to graphs that were either very small, very sparse or highly structured. Recent algorithmic advances (Timme et al 2009 New J. Phys. 11 023001) now make it possible to compute chromatic polynomials for moderately sized graphs of arbitrary structure and number of edges. Here we present chromatic polynomials of ensembles of random graphs with up to 30 vertices, over the entire range of edge density. We specifically focus on the locations of the zeros of the polynomial in the complex plane. The results indicate that the chromatic zeros of random graphs have a very consistent layout. In particular, the crossing point, the point at which the chromatic zeros with non-zero imaginary part approach the real axis, scales linearly with the average degree over most of the density range. While the scaling laws obtained are purely empirical, if they continue to hold in general there are significant implications: the crossing points of chromatic zeros in the thermodynamic limit separate systems with zero ground state entropy from systems with positive ground state entropy, the latter an exception to the third law of thermodynamics.

  1. Overlapped optics induced perfect coherent effects

    Science.gov (United States)

    Li, Jian Jie; Zang, Xiao Fei; Mao, Jun Fa; Tang, Min; Zhu, Yi Ming; Zhuang, Song Lin

    2013-12-01

    For traditional coherent effects, two separated identical point sources can be interfered with each other only when the optical path difference is integer number of wavelengths, leading to alternate dark and bright fringes for different optical path difference. For hundreds of years, such a perfect coherent condition seems insurmountable. However, in this paper, based on transformation optics, two separated in-phase identical point sources can induce perfect interference with each other without satisfying the traditional coherent condition. This shifting illusion media is realized by inductor-capacitor transmission line network. Theoretical analysis, numerical simulations and experimental results are performed to confirm such a kind of perfect coherent effect and it is found that the total radiation power of multiple elements system can be greatly enhanced. Our investigation may be applicable to National Ignition Facility (NIF), Inertial Confined Fusion (ICF) of China, LED lighting technology, terahertz communication, and so on.

  2. Overlapped optics induced perfect coherent effects.

    Science.gov (United States)

    Li, Jian Jie; Zang, Xiao Fei; Mao, Jun Fa; Tang, Min; Zhu, Yi Ming; Zhuang, Song Lin

    2013-12-20

    For traditional coherent effects, two separated identical point sources can be interfered with each other only when the optical path difference is integer number of wavelengths, leading to alternate dark and bright fringes for different optical path difference. For hundreds of years, such a perfect coherent condition seems insurmountable. However, in this paper, based on transformation optics, two separated in-phase identical point sources can induce perfect interference with each other without satisfying the traditional coherent condition. This shifting illusion media is realized by inductor-capacitor transmission line network. Theoretical analysis, numerical simulations and experimental results are performed to confirm such a kind of perfect coherent effect and it is found that the total radiation power of multiple elements system can be greatly enhanced. Our investigation may be applicable to National Ignition Facility (NIF), Inertial Confined Fusion (ICF) of China, LED lighting technology, terahertz communication, and so on.

  3. Graph Quasicontinuous Functions and Densely Continuous Forms

    Directory of Open Access Journals (Sweden)

    Lubica Hola

    2017-07-01

    Full Text Available Let $X, Y$ be topological spaces. A function $f: X \\to Y$ is said to be graph quasicontinuous if there is a quasicontinuous function $g: X \\to Y$ with the graph of $g$ contained in the closure of the graph of $f$. There is a close relation between the notions of graph quasicontinuous functions and minimal usco maps as well as the notions of graph quasicontinuous functions and densely continuous forms. Every function with values in a compact Hausdorff space is graph quasicontinuous; more generally every locally compact function is graph quasicontinuous.

  4. On P-transitive graphs and applications

    Directory of Open Access Journals (Sweden)

    Giacomo Lenzi

    2011-06-01

    Full Text Available We introduce a new class of graphs which we call P-transitive graphs, lying between transitive and 3-transitive graphs. First we show that the analogue of de Jongh-Sambin Theorem is false for wellfounded P-transitive graphs; then we show that the mu-calculus fixpoint hierarchy is infinite for P-transitive graphs. Both results contrast with the case of transitive graphs. We give also an undecidability result for an enriched mu-calculus on P-transitive graphs. Finally, we consider a polynomial time reduction from the model checking problem on arbitrary graphs to the model checking problem on P-transitive graphs. All these results carry over to 3-transitive graphs.

  5. Probing Factors Influencing Students' Graph Comprehension Regarding Four Operations in Kinematics Graphs

    Science.gov (United States)

    Phage, Itumeleng B.; Lemmer, Miriam; Hitge, Mariette

    2017-01-01

    Students' graph comprehension may be affected by the background of the students who are the readers or interpreters of the graph, their knowledge of the context in which the graph is set, and the inferential processes required by the graph operation. This research study investigated these aspects of graph comprehension for 152 first year…

  6. Domination parameters of a graph with added vertex

    Directory of Open Access Journals (Sweden)

    Maciej Zwierzchowski

    2004-01-01

    Full Text Available Let \\(G=(V,E\\ be a graph. A subset \\(D\\subseteq V\\ is a total dominating set of \\(G\\ if for every vertex \\(y\\in V\\ there is a vertex \\(x\\in D\\ with \\(xy\\in E\\. A subset \\(D\\subseteq V\\ is a strong dominating set of \\(G\\ if for every vertex \\(y\\in V-D\\ there is a vertex \\(x\\in D\\ with \\(xy\\in E\\ and \\(\\deg _{G}(x\\geq\\deg _{G}(y\\. The total domination number \\(\\gamma _{t}(G\\ (the strong domination number \\(\\gamma_{S}(G\\ is defined as the minimum cardinality of a total dominating set (a strong dominating set of \\(G\\. The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [Cockayne E. J., Dawes R. M., Hedetniemi S. T.: Total domination in graphs. Networks 10 (1980, 211–219], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [Pushpa Latha L., Sampathkumar E.: Strong weak domination and domination balance in a graph. Discrete Mathematics 161 (1996, 235–242]. By a subdivision of an edge \\(uv\\in E\\ we mean removing edge \\(uv\\, adding a new vertex \\(x\\, and adding edges \\(ux\\ and \\(vx\\. A graph obtained from \\(G\\ by subdivision an edge \\(uv\\in E\\ is denoted by \\(G\\oplus u_{x}v_{x}\\. The behaviour of the total domination number and the strong domination number of a graph \\(G\\oplus u_{x}v_{x}\\ is developed.

  7. A Hypergraph Dictatorship Test with Perfect Completeness

    Science.gov (United States)

    Chen, Victor

    A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based {operatorname{PCP}} construction. Such a test has oracle access to a collection of functions and determines whether all the functions are the same dictatorship, or all their low degree influences are o(1). Their test makes q ≥ 3 queries, has amortized query complexity 1+Oleft(log q/qright), but has an inherent loss of perfect completeness. In this paper we give an (adaptive) hypergraph dictatorship test that achieves both perfect completeness and amortized query complexity 1+Oleft(log q/qright).

  8. Optimal simulation of a perfect entangler

    International Nuclear Information System (INIS)

    Yu Nengkun; Duan Runyao; Ying Mingsheng

    2010-01-01

    A 2 x 2 unitary operation is called a perfect entangler if it can generate a maximally entangled state from some unentangled input. We study the following question: How many runs of a given two-qubit entangling unitary operation are required to simulate some perfect entangler with one-qubit unitary operations as free resources? We completely solve this problem by presenting an analytical formula for the optimal number of runs of the entangling operation. Our result reveals an entanglement strength of two-qubit unitary operations.

  9. Perfect 800 Advanced Strategies for Top Students

    CERN Document Server

    Celenti, Dan

    2010-01-01

    Getting into the nation's most competitive universities requires more than a good SAT score, it requires a perfect score. Perfect 800: SAT Math gives advanced students the tools needed to master the SAT math test. Covering areas including arithmetic concepts; algebra; geometry; and additional topics such as probability and weighted average, the book offers exposure to a wide range of degrees of difficulty in a holistic approach that allows students to experience the "real thing," including the impact of time constraints on their performance. By emphasizing critical thinking and analytic skills

  10. Lattice-Like Total Perfect Codes

    Directory of Open Access Journals (Sweden)

    Araujo Carlos

    2014-02-01

    Full Text Available A contribution is made to the classification of lattice-like total perfect codes in integer lattices Λn via pairs (G, Φ formed by abelian groups G and homomorphisms Φ: Zn → G. A conjecture is posed that the cited contribution covers all possible cases. A related conjecture on the unfinished work on open problems on lattice-like perfect dominating sets in Λn with induced components that are parallel paths of length > 1 is posed as well.

  11. Optimization of Perfect Absorbers with Multilayer Structures

    Science.gov (United States)

    Li Voti, Roberto

    2018-02-01

    We study wide-angle and broadband perfect absorbers with compact multilayer structures made of a sequence of ITO and TiN layers deposited onto a silver thick layer. An optimization procedure is introduced for searching the optimal thicknesses of the layers so as to design a perfect broadband absorber from 400 nm to 750 nm, for a wide range of angles of incidence from 0{°} to 50{°}, for both polarizations and with a low emissivity in the mid-infrared. We eventually compare the performances of several optimal structures that can be very promising for solar thermal energy harvesting and collectors.

  12. Two particles' repelling random walks on the complete graph

    OpenAIRE

    Chen, Jun

    2014-01-01

    We consider two particles' repelling random walks on complete graphs. In this model, each particle has higher probability to visit the vertices which have been seldom visited by the other one. By a dynamical approach we prove that the two particles' occupation measure asymptotically has small joint support almost surely if the repulsion is strong enough.

  13. Geometry of Graph Edit Distance Spaces

    OpenAIRE

    Jain, Brijnesh J.

    2015-01-01

    In this paper we study the geometry of graph spaces endowed with a special class of graph edit distances. The focus is on geometrical results useful for statistical pattern recognition. The main result is the Graph Representation Theorem. It states that a graph is a point in some geometrical space, called orbit space. Orbit spaces are well investigated and easier to explore than the original graph space. We derive a number of geometrical results from the orbit space representation, translate ...

  14. GraphMeta: Managing HPC Rich Metadata in Graphs

    Energy Technology Data Exchange (ETDEWEB)

    Dai, Dong; Chen, Yong; Carns, Philip; Jenkins, John; Zhang, Wei; Ross, Robert

    2016-01-01

    High-performance computing (HPC) systems face increasingly critical metadata management challenges, especially in the approaching exascale era. These challenges arise not only from exploding metadata volumes, but also from increasingly diverse metadata, which contains data provenance and arbitrary user-defined attributes in addition to traditional POSIX metadata. This ‘rich’ metadata is becoming critical to supporting advanced data management functionality such as data auditing and validation. In our prior work, we identified a graph-based model as a promising solution to uniformly manage HPC rich metadata due to its flexibility and generality. However, at the same time, graph-based HPC rich metadata anagement also introduces significant challenges to the underlying infrastructure. In this study, we first identify the challenges on the underlying infrastructure to support scalable, high-performance rich metadata management. Based on that, we introduce GraphMeta, a graphbased engine designed for this use case. It achieves performance scalability by introducing a new graph partitioning algorithm and a write-optimal storage engine. We evaluate GraphMeta under both synthetic and real HPC metadata workloads, compare it with other approaches, and demonstrate its advantages in terms of efficiency and usability for rich metadata management in HPC systems.

  15. PRIVATE GRAPHS – ACCESS RIGHTS ON GRAPHS FOR SEAMLESS NAVIGATION

    Directory of Open Access Journals (Sweden)

    W. Dorner

    2016-06-01

    Full Text Available After the success of GNSS (Global Navigational Satellite Systems and navigation services for public streets, indoor seems to be the next big development in navigational services, relying on RTLS – Real Time Locating Services (e.g. WIFI and allowing seamless navigation. In contrast to navigation and routing services on public streets, seamless navigation will cause an additional challenge: how to make routing data accessible to defined users or restrict access rights for defined areas or only to parts of the graph to a defined user group? The paper will present case studies and data from literature, where seamless and especially indoor navigation solutions are presented (hospitals, industrial complexes, building sites, but the problem of restricted access rights was only touched from a real world, but not a technical perspective. The analysis of case studies will show, that the objective of navigation and the different target groups for navigation solutions will demand well defined access rights and require solutions, how to make only parts of a graph to a user or application available to solve a navigational task. The paper will therefore introduce the concept of private graphs, which is defined as a graph for navigational purposes covering the street, road or floor network of an area behind a public street and suggest different approaches how to make graph data for navigational purposes available considering access rights and data protection, privacy and security issues as well.

  16. Mechanical Energy Changes in Perfectly Inelastic Collisions

    Science.gov (United States)

    Mungan, Carl E.

    2013-01-01

    Suppose a block of mass "m"[subscript 1] traveling at speed "v"[subscript 1] makes a one-dimensional perfectly inelastic collision with another block of mass "m"[subscript 2]. What else does one need to know to calculate the fraction of the mechanical energy that is dissipated in the collision? (Contains 1 figure.)

  17. Perfectly Secure Oblivious RAM without Random Oracles

    DEFF Research Database (Denmark)

    Damgård, Ivan Bjerre; Meldgaard, Sigurd Torkel; Nielsen, Jesper Buus

    2011-01-01

    We present an algorithm for implementing a secure oblivious RAM where the access pattern is perfectly hidden in the information theoretic sense, without assuming that the CPU has access to a random oracle. In addition we prove a lower bound on the amount of randomness needed for implementing...... an information theoretically secure oblivious RAM....

  18. Perfect and Periphrastic Passive Constructions in Danish

    DEFF Research Database (Denmark)

    Bjerre, Tavs; Bjerre, Anne

    2007-01-01

    This paper gives an account of the event and argument structure of past participles and the linking between argument structure and valence structure. It further accounts for how participles form perfect and passiv constructions with auxiliaries. We assume that the same participle form is used in ...

  19. Le Perfectionnement en Phonetique (Perfecting Phonetics)

    Science.gov (United States)

    Laroche-Bouvy, Danielle

    1975-01-01

    This article describes the programs of the Institut d'Etudes Linguistiques et Phonetiques, located in Paris. The program focuses on perfecting the students' phonetic production of French. Both curriculum and teaching methods are described, as well as a course in phonetics for future teachers of French. (Text is in French.) (CLK)

  20. Unconditionally stable perfectly matched layer boundary conditions

    NARCIS (Netherlands)

    De Raedt, H.; Michielsen, K.

    2007-01-01

    A brief review is given of a systematic, product-formula based approach to construct unconditionally stable algorithms for solving the time-dependent Maxwell equations. The fundamental difficulties that arise when we want to incorporate uniaxial perfectly matched layer boundary conditions into this

  1. Reshaping the perfect electrical conductor cylinder arbitrarily

    International Nuclear Information System (INIS)

    Chen Huanyang; Zhang Xiaohe; Luo Xudong; Ma Hongru; Chan Cheting

    2008-01-01

    A general method is proposed to design a cylindrical cloak, concentrator and superscatterer with an arbitrary cross section. The method is demonstrated by the design of a perfect electrical conductor (PEC) reshaper which is able to reshape a PEC cylinder arbitrarily by combining the concept of cloak, concentrator and superscatterer together. Numerical simulations are performed to demonstrate its properties.

  2. Diamagnetic expansions for perfect quantum gases

    DEFF Research Database (Denmark)

    Briet, Philippe; Cornean, Horia; Louis, Delphine

    2006-01-01

    In this work we study the diamagnetic properties of a perfect quantum gas in the presence of a constant magnetic field of intensity B. We investigate the Gibbs semigroup associated with the one particle operator at finite volume, and study its Taylor series with respect to the field parameter ome...

  3. Box graphs and resolutions I

    Directory of Open Access Journals (Sweden)

    Andreas P. Braun

    2016-04-01

    Full Text Available Box graphs succinctly and comprehensively characterize singular fibers of elliptic fibrations in codimension two and three, as well as flop transitions connecting these, in terms of representation theoretic data. We develop a framework that provides a systematic map between a box graph and a crepant algebraic resolution of the singular elliptic fibration, thus allowing an explicit construction of the fibers from a singular Weierstrass or Tate model. The key tool is what we call a fiber face diagram, which shows the relevant information of a (partial toric triangulation and allows the inclusion of more general algebraic blowups. We shown that each such diagram defines a sequence of weighted algebraic blowups, thus providing a realization of the fiber defined by the box graph in terms of an explicit resolution. We show this correspondence explicitly for the case of SU(5 by providing a map between box graphs and fiber faces, and thereby a sequence of algebraic resolutions of the Tate model, which realizes each of the box graphs.

  4. Hierarchical organisation of causal graphs

    International Nuclear Information System (INIS)

    Dziopa, P.

    1993-01-01

    This paper deals with the design of a supervision system using a hierarchy of models formed by graphs, in which the variables are the nodes and the causal relations between the variables of the arcs. To obtain a representation of the variables evolutions which contains only the relevant features of their real evolutions, the causal relations are completed with qualitative transfer functions (QTFs) which produce roughly the behaviour of the classical transfer functions. Major improvements have been made in the building of the hierarchical organization. First, the basic variables of the uppermost level and the causal relations between them are chosen. The next graph is built by adding intermediary variables to the upper graph. When the undermost graph has been built, the transfer functions parameters corresponding to its causal relations are identified. The second task consists in the upwelling of the information from the undermost graph to the uppermost one. A fusion procedure of the causal relations has been designed to compute the QFTs relevant for each level. This procedure aims to reduce the number of parameters needed to represent an evolution at a high level of abstraction. These techniques have been applied to the hierarchical modelling of nuclear process. (authors). 8 refs., 12 figs

  5. Integer Flows and Circuit Covers of Graphs and Signed Graphs

    Science.gov (United States)

    Cheng, Jian

    The work in Chapter 2 is motivated by Tutte and Jaeger's pioneering work on converting modulo flows into integer-valued flows for ordinary graphs. For a signed graphs (G, sigma), we first prove that for each k ∈ {2, 3}, if (G, sigma) is (k - 1)-edge-connected and contains an even number of negative edges when k = 2, then every modulo k-flow of (G, sigma) can be converted into an integer-valued ( k + 1)-ow with a larger or the same support. We also prove that if (G, sigma) is odd-(2p+1)-edge-connected, then (G, sigma) admits a modulo circular (2 + 1/ p)-flows if and only if it admits an integer-valued circular (2 + 1/p)-flows, which improves all previous result by Xu and Zhang (DM2005), Schubert and Steffen (EJC2015), and Zhu (JCTB2015). Shortest circuit cover conjecture is one of the major open problems in graph theory. It states that every bridgeless graph G contains a set of circuits F such that each edge is contained in at least one member of F and the length of F is at most 7/5∥E(G)∥. This concept was recently generalized to signed graphs by Macajova et al. (JGT2015). In Chapter 3, we improve their upper bound from 11∥E( G)∥ to 14/3 ∥E(G)∥, and if G is 2-edgeconnected and has even negativeness, then it can be further reduced to 11/3 ∥E(G)∥. Tutte's 3-flow conjecture has been studied by many graph theorists in the last several decades. As a new approach to this conjecture, DeVos and Thomassen considered the vectors as ow values and found that there is a close relation between vector S1-flows and integer 3-NZFs. Motivated by their observation, in Chapter 4, we prove that if a graph G admits a vector S1-flow with rank at most two, then G admits an integer 3-NZF. The concept of even factors is highly related to the famous Four Color Theorem. We conclude this dissertation in Chapter 5 with an improvement of a recent result by Chen and Fan (JCTB2016) on the upperbound of even factors. We show that if a graph G contains an even factor, then it

  6. Algorithms for Planar Graphs and Graphs in Metric Spaces

    DEFF Research Database (Denmark)

    Wulff-Nilsen, Christian

    preprocessing time, an O(n log n) time algorithm for the replacement paths problem, and a min st-cut oracle with nearlinear preprocessing time. We also give improved time bounds for computing various graph invariants such as diameter and girth. In the second part, we consider stretch factor problems...... a graph with new edges while minimizing stretch factor. The third and final part of the thesis deals with the Steiner tree problem in the plane equipped with a weighted fixed orientation metric. Here, we give an improved theoretical analysis of the strength of pruning techniques applied by many Steiner...

  7. The paired-domination and the upper paired-domination numbers of graphs

    Directory of Open Access Journals (Sweden)

    Włodzimierz Ulatowski

    2015-01-01

    Full Text Available In this paper we continue the study of paired-domination in graphs. A paired-dominating set, abbreviated PDS, of a graph \\(G\\ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of \\(G\\, denoted by \\(\\gamma_{p}(G\\, is the minimum cardinality of a PDS of \\(G\\. The upper paired-domination number of \\(G\\, denoted by \\(\\Gamma_{p}(G\\, is the maximum cardinality of a minimal PDS of \\(G\\. Let \\(G\\ be a connected graph of order \\(n\\geq 3\\. Haynes and Slater in [Paired-domination in graphs, Networks 32 (1998, 199-206], showed that \\(\\gamma_{p}(G\\leq n-1\\ and they determine the extremal graphs \\(G\\ achieving this bound. In this paper we obtain analogous results for \\(\\Gamma_{p}(G\\. Dorbec, Henning and McCoy in [Upper total domination versus upper paired-domination, Questiones Mathematicae 30 (2007, 1-12] determine \\(\\Gamma_{p}(P_n\\, instead in this paper we determine \\(\\Gamma_{p}(C_n\\. Moreover, we describe some families of graphs \\(G\\ for which the equality \\(\\gamma_{p}(G=\\Gamma_{p}(G\\ holds.

  8. An algebraic approach to graph codes

    DEFF Research Database (Denmark)

    Pinero, Fernando

    theory as evaluation codes. Chapter three consists of the introduction to graph based codes, such as Tanner codes and graph codes. In Chapter four, we compute the dimension of some graph based codes with a result combining graph based codes and subfield subcodes. Moreover, some codes in chapter four...... are optimal or best known for their parameters. In chapter five we study some graph codes with Reed–Solomon component codes. The underlying graph is well known and widely used for its good characteristics. This helps us to compute the dimension of the graph codes. We also introduce a combinatorial concept...... related to the iterative encoding of graph codes with MDS component code. The last chapter deals with affine Grassmann codes and Grassmann codes. We begin with some previously known codes and prove that they are also Tanner codes of the incidence graph of the point–line partial geometry...

  9. Nodal Statistics on Quantum Graphs

    Science.gov (United States)

    Alon, Lior; Band, Ram; Berkolaiko, Gregory

    2018-03-01

    It has been suggested that the distribution of the suitably normalized number of zeros of Laplacian eigenfunctions contains information about the geometry of the underlying domain. We study this distribution (more precisely, the distribution of the "nodal surplus") for Laplacian eigenfunctions of a metric graph. The existence of the distribution is established, along with its symmetry. One consequence of the symmetry is that the graph's first Betti number can be recovered as twice the average nodal surplus of its eigenfunctions. Furthermore, for graphs with disjoint cycles it is proven that the distribution has a universal form—it is binomial over the allowed range of values of the surplus. To prove the latter result, we introduce the notion of a local nodal surplus and study its symmetry and dependence properties, establishing that the local nodal surpluses of disjoint cycles behave like independent Bernoulli variables.

  10. Graph modeling systems and methods

    Science.gov (United States)

    Neergaard, Mike

    2015-10-13

    An apparatus and a method for vulnerability and reliability modeling are provided. The method generally includes constructing a graph model of a physical network using a computer, the graph model including a plurality of terminating vertices to represent nodes in the physical network, a plurality of edges to represent transmission paths in the physical network, and a non-terminating vertex to represent a non-nodal vulnerability along a transmission path in the physical network. The method additionally includes evaluating the vulnerability and reliability of the physical network using the constructed graph model, wherein the vulnerability and reliability evaluation includes a determination of whether each terminating and non-terminating vertex represents a critical point of failure. The method can be utilized to evaluate wide variety of networks, including power grid infrastructures, communication network topologies, and fluid distribution systems.

  11. On the graph turnpike problem

    KAUST Repository

    Feder, Tomás

    2009-06-01

    Results on graph turnpike problem without distinctness, including its NP-completeness, and an O(m+n log n) algorithm, is presented. The usual turnpike problem has all pairwise distances given, but does not specify which pair of vertices w e corresponds to. There are two other problems that can be viewed as special cases of the graph turnpike problem, including the bandwidth problem and the low-distortion graph embedding problem. The aim for the turnpike problem in the NP-complete is to orient the edges with weights w i in either direction so that when the whole cycle is transversed in the real line, it returns to a chosen starting point for the cycle. An instance of the turnpike problem with or without distinctness is uniquely mappable if there exists at most one solution up to translation and choice of orientation.

  12. Negation switching invariant signed graphs

    Directory of Open Access Journals (Sweden)

    Deepa Sinha

    2014-04-01

    Full Text Available A signed graph (or, $sigraph$ in short is a graph G in which each edge x carries a value $\\sigma(x \\in \\{-, +\\}$ called its sign. Given a sigraph S, the negation $\\eta(S$ of the sigraph S is a sigraph obtained from S by reversing the sign of every edge of S. Two sigraphs $S_{1}$ and $S_{2}$ on the same underlying graph are switching equivalent if it is possible to assign signs `+' (`plus' or `-' (`minus' to vertices of $S_{1}$ such that by reversing the sign of each of its edges that has received opposite signs at its ends, one obtains $S_{2}$. In this paper, we characterize sigraphs which are negation switching invariant and also see for what sigraphs, S and $\\eta (S$ are signed isomorphic.

  13. The fascinating world of graph theory

    CERN Document Server

    Benjamin, Arthur; Zhang, Ping

    2015-01-01

    Graph theory goes back several centuries and revolves around the study of graphs-mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics-and some of its most famous problems. The Fascinating World of Graph Theory explores the questions and puzzles that have been studied, and often solved, through graph theory. This book looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducin

  14. An intersection graph of straight lines

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2002-01-01

    G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.......G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is....

  15. Graph-based modelling in engineering

    CERN Document Server

    Rysiński, Jacek

    2017-01-01

    This book presents versatile, modern and creative applications of graph theory in mechanical engineering, robotics and computer networks. Topics related to mechanical engineering include e.g. machine and mechanism science, mechatronics, robotics, gearing and transmissions, design theory and production processes. The graphs treated are simple graphs, weighted and mixed graphs, bond graphs, Petri nets, logical trees etc. The authors represent several countries in Europe and America, and their contributions show how different, elegant, useful and fruitful the utilization of graphs in modelling of engineering systems can be. .

  16. Graph Processing on GPUs: A Survey

    DEFF Research Database (Denmark)

    Shi, Xuanhua; Zheng, Zhigao; Zhou, Yongluan

    2018-01-01

    In the big data era, much real-world data can be naturally represented as graphs. Consequently, many application domains can be modeled as graph processing. Graph processing, especially the processing of the large-scale graphs with the number of vertices and edges in the order of billions or even......, utilizing GPU to accelerate graph processing proves to be a promising solution. This article surveys the key issues of graph processing on GPUs, including data layout, memory access pattern, workload mapping, and specific GPU programming. In this article, we summarize the state-of-the-art research on GPU...

  17. Quantum centrality testing on directed graphs via P T -symmetric quantum walks

    Science.gov (United States)

    Izaac, J. A.; Wang, J. B.; Abbott, P. C.; Ma, X. S.

    2017-09-01

    Various quantum-walk-based algorithms have been proposed to analyze and rank the centrality of graph vertices. However, issues arise when working with directed graphs: the resulting non-Hermitian Hamiltonian leads to nonunitary dynamics, and the total probability of the quantum walker is no longer conserved. In this paper, we discuss a method for simulating directed graphs using P T -symmetric quantum walks, allowing probability-conserving nonunitary evolution. This method is equivalent to mapping the directed graph to an undirected, yet weighted, complete graph over the same vertex set, and can be extended to cover interdependent networks of directed graphs. Previous work has shown centrality measures based on the continuous-time quantum walk provide an eigenvectorlike quantum centrality; using the P T -symmetric framework, we extend these centrality algorithms to directed graphs with a significantly reduced Hilbert space compared to previous proposals. In certain cases, this centrality measure provides an advantage over classical algorithms used in network analysis, for example, by breaking vertex rank degeneracy. Finally, we perform a statistical analysis over ensembles of random graphs, and show strong agreement with the classical PageRank measure on directed acyclic graphs.

  18. Graph topologies on closed multifunctions

    Directory of Open Access Journals (Sweden)

    Giuseppe Di Maio

    2003-10-01

    Full Text Available In this paper we study function space topologies on closed multifunctions, i.e. closed relations on X x Y using various hypertopologies. The hypertopologies are in essence, graph topologies i.e topologies on functions considered as graphs which are subsets of X x Y . We also study several topologies, including one that is derived from the Attouch-Wets filter on the range. We state embedding theorems which enable us to generalize and prove some recent results in the literature with the use of known results in the hyperspace of the range space and in the function space topologies of ordinary functions.

  19. XML Graphs in Program Analysis

    DEFF Research Database (Denmark)

    Møller, Anders; Schwartzbach, Michael Ignatieff

    2007-01-01

    XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation...... of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey four very different applications: XML in Java, Java Servlets and JSP, transformations between XML and non-XML data, and XSLT....

  20. Scalar fields on star graphs

    OpenAIRE

    Andersson, Mattias

    2011-01-01

     A star graph consists of a vertex to which a set of edges are connected. Such an object can be used to, among other things, model the electromagnetic properties of quantum wires. A scalar field theory is constructed on the star graph and its properties are investigated. It turns out that there exist Kirchoff's rules for the conserved charges in the system leading to restrictions of the possible type of boundary conditions at the vertex. Scale invariant boundary conditions are investigated in...

  1. Completely Described Undirected Graph Structure

    Directory of Open Access Journals (Sweden)

    G. S. Ivanova

    2016-01-01

    Full Text Available The objects of research are undirected graphs. The paper considers a problem of their isomorphism. A literature analysis of its solution, has shown that there is no way to define a complete graph invariant in the form of unique structural characteristics of each its vertex, which has a computational complexity of definition better than О (n 4 .The work objective is to provide the characteristics of the graph structure, which could be used to solve the problem of their isomorphism for a time better than О (n 4 . As such characteristics, the paper proposes to use the set of codes of tree roots of all the shortest - in terms of the number of edges - paths from each vertex to the others, uniquely defining the structure of each tree. It proves the theorem that it is possible to reduce the problem of isomorphism of the undirected graphs to the isomorphism problem of their splitting into the trees of all the shortest - in terms of the number of edges - paths of each vertex to the others. An algorithm to construct the shortest paths from each vertex to all others and to compute codes of their vertices has been developed. As the latter, are used Aho-codes, which find application in recognising the isomorphism of trees. The computational complexity to obtain structural characteristics of vertices has been estimated to be about О (n 3 .The pilot studies involved the full-scale experiment using the developed complex programmes to generate raw data, i.e. analytic representation of the graph with the number of vertices equal to 1200, and a programme to provide codes of the tree roots. To have an estimate of - "the worst" in terms of time - complexity of expansion algorithm of graphs into trees of the shortest paths and define the codes of their roots has been an experimentally studied how the number of tree vertices depends on the graph density. For the worst case was obtained a dependence of the number of tree vertices on the number of graph vertices

  2. Some Invariants of Jahangir Graphs

    Directory of Open Access Journals (Sweden)

    Mobeen Munir

    2017-01-01

    Full Text Available In this report, we compute closed forms of M-polynomial, first and second Zagreb polynomials and forgotten polynomial for Jahangir graphs Jn,m for all values of m and n. From the M-polynomial, we recover many degree-based topological indices such as first and second Zagreb indices, modified Zagreb index, Symmetric division index, etc. We also compute harmonic index, first and second multiple Zagreb indices and forgotten index of Jahangir graphs. Our results are extensions of many existing results.

  3. Graph abstraction and abstract graph transformations (Amended version)

    NARCIS (Netherlands)

    Boneva, I.B.; Kreiker, Jörg; Kurban, M.E.; Rensink, Arend; Zambon, Eduardo

    2012-01-01

    Many important systems such as concurrent heap-manipulating programs, communication networks, or distributed algorithms, are hard to verify due to their inherent dynamics and unboundedness. Graphs are an intuitive representation for the states of these systems, where transitions can be conveniently

  4. Multiple graph regularized protein domain ranking

    KAUST Repository

    Wang, Jim Jing-Yan

    2012-11-19

    Background: Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods.Results: To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods.Conclusion: The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications. 2012 Wang et al; licensee BioMed Central Ltd.

  5. Multiple graph regularized protein domain ranking.

    Science.gov (United States)

    Wang, Jim Jing-Yan; Bensmail, Halima; Gao, Xin

    2012-11-19

    Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

  6. Multiple graph regularized protein domain ranking

    Directory of Open Access Journals (Sweden)

    Wang Jim

    2012-11-01

    Full Text Available Abstract Background Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. Results To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. Conclusion The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

  7. Thermodynamical stability for a perfect fluid

    Energy Technology Data Exchange (ETDEWEB)

    Fang, Xiongjun; Jing, Jiliang [Hunan Normal University, Department of Physics, Key Laboratory of Low Dimensional Quantum Structures and Quantum Control of Ministry of Education, and Synergetic Innovation Center for Quantum Effects and Applications, Changsha, Hunan (China); He, Xiaokai [Hunan Normal University, Department of Physics, Key Laboratory of Low Dimensional Quantum Structures and Quantum Control of Ministry of Education, and Synergetic Innovation Center for Quantum Effects and Applications, Changsha, Hunan (China); Hunan First Normal University, School of Mathematics and Computational Science, Changsha (China)

    2017-12-15

    According to the maximum entropy principle, it has been proved that the gravitational field equations could be derived by the extrema of the total entropy for a perfect fluid, which implies that thermodynamic relations contain information as regards gravity. In this manuscript, we obtain a criterion for the thermodynamical stability of an adiabatic, self-gravitating perfect fluid system by the second variation of the total entropy. We show, for Einstein's gravity with spherical symmetry spacetime, that the criterion is consistent with that for the dynamical stability derived by Chandrasekhar and Wald. We also find that the criterion could be applied to cases without spherical symmetry, or under general perturbations. The result further establishes the connection between thermodynamics and gravity. (orig.)

  8. Thermodynamical stability for a perfect fluid

    Science.gov (United States)

    Fang, Xiongjun; He, Xiaokai; Jing, Jiliang

    2017-12-01

    According to the maximum entropy principle, it has been proved that the gravitational field equations could be derived by the extrema of the total entropy for a perfect fluid, which implies that thermodynamic relations contain information as regards gravity. In this manuscript, we obtain a criterion for the thermodynamical stability of an adiabatic, self-gravitating perfect fluid system by the second variation of the total entropy. We show, for Einstein's gravity with spherical symmetry spacetime, that the criterion is consistent with that for the dynamical stability derived by Chandrasekhar and Wald. We also find that the criterion could be applied to cases without spherical symmetry, or under general perturbations. The result further establishes the connection between thermodynamics and gravity.

  9. Nonminimal coupling of perfect fluids to curvature

    International Nuclear Information System (INIS)

    Bertolami, Orfeu; Lobo, Francisco S. N.; Paramos, Jorge

    2008-01-01

    In this work, we consider different forms of relativistic perfect fluid Lagrangian densities that yield the same gravitational field equations in general relativity (GR). A particularly intriguing example is the case with couplings of the form [1+f 2 (R)]L m , where R is the scalar curvature, which induces an extra force that depends on the form of the Lagrangian density. It has been found that, considering the Lagrangian density L m =p, where p is the pressure, the extra-force vanishes. We argue that this is not the unique choice for the matter Lagrangian density, and that more natural forms for L m do not imply the vanishing of the extra force. Particular attention is paid to the impact on the classical equivalence between different Lagrangian descriptions of a perfect fluid.

  10. Population growth rates in perfect contraceptive populations.

    Science.gov (United States)

    Udry, J R; Bauman, K E; Chase, C L

    1973-07-01

    Abstract Eventually, world population must cease to grow. In many countries attempts are made to decrease population growth by providing family planning services to all who want to prevent pregnancies. In this paper we use the concept 'perfect contraceptive population',(1) - a population in which no unwanted births occur - to derive estimates of the maximum contribution that prevention of unwanted births might make toward attaining a zero rate of natural increase in population.

  11. Another Class of Perfect Nonlinear Polynomial Functions

    Directory of Open Access Journals (Sweden)

    Menglong Su

    2013-01-01

    Full Text Available Perfect nonlinear (PN functions have been an interesting subject of study for a long time and have applications in coding theory, cryptography, combinatorial designs, and so on. In this paper, the planarity of the trinomials xpk+1+ux2+vx2pk over GF(p2k are presented. This class of PN functions are all EA-equivalent to x2.

  12. The perfect crime: myth or reality?

    Science.gov (United States)

    Fanton, L; Miras, A; Tilhet-Coartet, S; Achache, P; Malicier, D

    1998-09-01

    The primum movens of a forensic autopsy is to track down the crime. The perfect crime can be defined as one which will never be suspected and/or one for which the criminal will never be arrested. We have reported several cases that have been adjudicated or are being adjudicated, and we show how actual homicides could have been taken for accidental deaths, suicides, or even natural deaths.

  13. Evolutionary stability of mixed strategies on graphs

    International Nuclear Information System (INIS)

    Li, Yan; Liu, Xinsheng; Claussen, Jens Christian

    2016-01-01

    Up to the present time, the study of evolutionary dynamics mostly focused on pure strategy games in finite discrete strategy space, either in well-mixed or structured populations. In this paper, we study mixed strategy games in continuous strategy space on graphs of degree k . Each player is arranged on a vertex of the graph. The edges denote the interaction between two individuals. In the limit of weak selection, we first derive the payoff functions of two mixed strategies under three different updating rules, named birth–death, death–birth and imitation. Then we obtain the conditions for a strategy being a continuously stable strategy (CSS), and we also confirm that the equilibrium distribution corresponding to the CSS is neighborhood attracting and strongly uninvadable. Finally, we apply our theory to the prisoner’s dilemma and the snowdrift game to obtain possible CSS. Simulations are performed for the two special games and the results are well consistent with the conclusions we made. (paper)

  14. Graph reconstruction with a betweenness oracle

    DEFF Research Database (Denmark)

    Abrahamsen, Mikkel; Bodwin, Greg; Rotenberg, Eva

    2016-01-01

    Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a blackbox oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair....... Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: 1. Reconstruction of general graphs in O(n2) queries 2. Reconstruction...... of degree-bounded graphs in Õ(n3/2) queries 3. Reconstruction of geodetic degree-bounded graphs in Õ(n) queries In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem....

  15. Use of Spatial Transformations in Graph Comprehension

    National Research Council Canada - National Science Library

    Trickett, Susan B; Trafton, J. G

    2004-01-01

    Current theories of graph comprehension are largely silent about the processes by which inferences are made from graphs, although it is apparent that people are able to make such inferences. In Trickett & Trafton (2004...

  16. Humidity Graphs for All Seasons.

    Science.gov (United States)

    Esmael, F.

    1982-01-01

    In a previous article in this journal (Vol. 17, p358, 1979), a wet-bulb depression table was recommended for two simple experiments to determine relative humidity. However, the use of a graph is suggested because it gives the relative humidity directly from the wet and dry bulb readings. (JN)

  17. A Problem in Graph Theory

    Indian Academy of Sciences (India)

    Home; Journals; Resonance – Journal of Science Education; Volume 12; Issue 1. A Problem in Graph Theory. K P Savithri. Think It Over Volume 12 Issue 1 January 2007 pp 81-81. Fulltext. Click here to view fulltext PDF. Permanent link: http://www.ias.ac.in/article/fulltext/reso/012/01/0081-0081. Author Affiliations.

  18. Box graphs and singular fibers

    International Nuclear Information System (INIS)

    Hayashi, Hirotaka; Lawrie, Craig; Morrison, David R.; Schäfer-Nameki, Sakura

    2014-01-01

    We determine the higher codimension fibers of elliptically fibered Calabi-Yau fourfolds with section by studying the three-dimensional N=2 supersymmetric gauge theory with matter which describes the low energy effective theory of M-theory compactified on the associated Weierstrass model, a singular model of the fourfold. Each phase of the Coulomb branch of this theory corresponds to a particular resolution of the Weierstrass model, and we show that these have a concise description in terms of decorated box graphs based on the representation graph of the matter multiplets, or alternatively by a class of convex paths on said graph. Transitions between phases have a simple interpretation as “flopping' of the path, and in the geometry correspond to actual flop transitions. This description of the phases enables us to enumerate and determine the entire network between them, with various matter representations for all reductive Lie groups. Furthermore, we observe that each network of phases carries the structure of a (quasi-)minuscule representation of a specific Lie algebra. Interpreted from a geometric point of view, this analysis determines the generators of the cone of effective curves as well as the network of flop transitions between crepant resolutions of singular elliptic Calabi-Yau fourfolds. From the box graphs we determine all fiber types in codimensions two and three, and we find new, non-Kodaira, fiber types for E 6 , E 7 and E 8

  19. Ancestral Genres of Mathematical Graphs

    Science.gov (United States)

    Gerofsky, Susan

    2011-01-01

    Drawing from sources in gesture studies, cognitive science, the anthropology of religion and art/architecture history, this article explores cultural, bodily and cosmological resonances carried (unintentionally) by mathematical graphs on Cartesian coordinates. Concepts of asymmetric bodily spaces, grids, orthogonality, mapping and sacred spaces…

  20. Constructing Knowledge Graphs of Depression

    NARCIS (Netherlands)

    Huang, Zhisheng; Yang, Jie; van Harmelen, Frank; Hu, Qing

    2017-01-01

    Knowledge Graphs have been shown to be useful tools for integrating multiple medical knowledge sources, and to support such tasks as medical decision making, literature retrieval, determining healthcare quality indicators, co-morbodity analysis and many others. A large number of medical knowledge

  1. Contracting a planar graph efficiently

    DEFF Research Database (Denmark)

    Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam

    2017-01-01

    We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying th...

  2. Fixation Time for Evolutionary Graphs

    Science.gov (United States)

    Nie, Pu-Yan; Zhang, Pei-Ai

    Evolutionary graph theory (EGT) is recently proposed by Lieberman et al. in 2005. EGT is successful for explaining biological evolution and some social phenomena. It is extremely important to consider the time of fixation for EGT in many practical problems, including evolutionary theory and the evolution of cooperation. This study characterizes the time to asymptotically reach fixation.

  3. From graphs to free products

    Indian Academy of Sciences (India)

    Examples: Some explicit computations. Throughout this section, we will assume that ( , μ) is a finite, connected, weighted graph. The adjacency matrix of (which, by abuse of notation, will also be denoted by ) is, as usual, the symmetric matrix with rows and columns indexed by the vertex set V of and. (v, w) = |{e ∈ E : s(e) = v, ...

  4. Affect and Graphing Calculator Use

    Science.gov (United States)

    McCulloch, Allison W.

    2011-01-01

    This article reports on a qualitative study of six high school calculus students designed to build an understanding about the affect associated with graphing calculator use in independent situations. DeBellis and Goldin's (2006) framework for affect as a representational system was used as a lens through which to understand the ways in which…

  5. On dominator colorings in graphs

    Indian Academy of Sciences (India)

    A dominator coloring of a graph is a proper coloring of in which every vertex dominates every vertex of at least one color class. The minimum number of colors required for a dominator coloring of is called the dominator chromatic number of and is denoted by d ( G ) . In this paper we present several results on ...

  6. NON-SELF-ADJOINT GRAPHS

    Czech Academy of Sciences Publication Activity Database

    Hussein, A.; Krejčiřík, David; Siegl, P.

    2015-01-01

    Roč. 367, č. 4 (2015), s. 2921-2957 ISSN 0002-9947 R&D Projects: GA ČR GAP203/11/0701 Institutional support: RVO:61389005 Keywords : Laplacians on metric graphs * non-self-adjoint boundary conditions * similarity transforms to self-adjoint operators * Riesz basis Subject RIV: BE - Theoretical Physics Impact factor: 1.196, year: 2015

  7. Application of graph database for analytical tasks

    OpenAIRE

    Günzl, Richard

    2014-01-01

    This diploma thesis is about graph databases, which belong to the category of database systems known as NoSQL databases, but graph databases are beyond NoSQL databases. Graph databases are useful in many cases thanks to native storing of interconnections between data, which brings advantageous properties in comparison with traditional relational database system, especially in querying. The main goal of the thesis is: to describe principles, properties and advantages of graph database; to desi...

  8. Bond graph modeling of centrifugal compression systems

    OpenAIRE

    Uddin, Nur; Gravdahl, Jan Tommy

    2015-01-01

    A novel approach to model unsteady fluid dynamics in a compressor network by using a bond graph is presented. The model is intended in particular for compressor control system development. First, we develop a bond graph model of a single compression system. Bond graph modeling offers a different perspective to previous work by modeling the compression system based on energy flow instead of fluid dynamics. Analyzing the bond graph model explains the energy flow during compressor surge. Two pri...

  9. A Graph Calculus for Predicate Logic

    Directory of Open Access Journals (Sweden)

    Paulo A. S. Veloso

    2013-03-01

    Full Text Available We introduce a refutation graph calculus for classical first-order predicate logic, which is an extension of previous ones for binary relations. One reduces logical consequence to establishing that a constructed graph has empty extension, i. e. it represents bottom. Our calculus establishes that a graph has empty extension by converting it to a normal form, which is expanded to other graphs until we can recognize conflicting situations (equivalent to a formula and its negation.

  10. Unsupervised Deep Haar Scattering on Graphs

    OpenAIRE

    Chen, Xu; Cheng, Xiuyuan; Mallat, Stéphane

    2014-01-01

    The classification of high-dimensional data defined on graphs is particularly difficult when the graph geometry is unknown. We introduce a Haar scattering transform on graphs, which computes invariant signal descriptors. It is implemented with a deep cascade of additions, subtractions and absolute values, which iteratively compute orthogonal Haar wavelet transforms. Multiscale neighborhoods of unknown graphs are estimated by minimizing an average total variation, with a pair matching algorith...

  11. On m-Neighbourly Irregular Instuitionistic Fuzzy Graphs

    OpenAIRE

    N.R.Santhi Maheswari; C.Sekar

    2016-01-01

    In this paper, m-neighbourly irregular intuitionistic fuzzy graphs and m- neighbourly totally irregular intuitionistic fuzzy graphs are defined. Relation between m-neighbourly irregular intuitionistic fuzzy graph and m-neighbourly totally irregular intuitionistic fuzzy graph are discussed.

  12. Construction of cycle double covers for certain classes of graphs

    NARCIS (Netherlands)

    Hoede, C.; Kriesell, M.; Uttuggadewa, S.

    2000-01-01

    We introduce two classes of graphs, Indonesian graphs and $k$-doughnut graphs. Cycle double covers are constructed for these classes. In case of doughnut graphs this is done for the values $k=1,2,3$ and 4.

  13. Graph Partitioning Models for Parallel Computing

    Energy Technology Data Exchange (ETDEWEB)

    Hendrickson, B.; Kolda, T.G.

    1999-03-02

    Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.

  14. Modeling Software Evolution using Algebraic Graph Rewriting

    NARCIS (Netherlands)

    Ciraci, S.; van den Broek, P.M.; Avgeriou, P.; Zdun, U.; Borne, I.

    We show how evolution requests can be formalized using algebraic graph rewriting. In particular, we present a way to convert the UML class diagrams to colored graphs. Since changes in software may effect the relation between the methods of classes, our colored graph representation also employs the

  15. My Bar Graph Tells a Story

    Science.gov (United States)

    McMillen, Sue; McMillen, Beth

    2010-01-01

    Connecting stories to qualitative coordinate graphs has been suggested as an effective instructional strategy. Even students who are able to "create" bar graphs may struggle to correctly "interpret" them. Giving children opportunities to work with qualitative graphs can help them develop the skills to interpret, describe, and compare information…

  16. A Type Graph Model for Java Programs

    NARCIS (Netherlands)

    Rensink, Arend; Zambon, Eduardo

    2009-01-01

    In this report we present a type graph that models all executable constructs of the Java programming language. Such a model is useful for any graph-based technique that relies on a representation of Java programs as graphs. The model can be regarded as a common representation to which all Java

  17. A Type Graph Model for Java Programs

    NARCIS (Netherlands)

    Rensink, Arend; Zambon, Eduardo; Lee, D.; Lopes, A.; Poetzsch-Heffter, A.

    2009-01-01

    In this work we present a type graph that models all executable constructs of the Java programming language. Such a model is useful for any graph-based technique that relies on a representation of Java programs as graphs. The model can be regarded as a common representation to which all Java syntax

  18. Cycles in weighted graphs and related topics

    NARCIS (Netherlands)

    Zhang, Shenggui

    2002-01-01

    This thesis contains results on paths andcycles in graphs andon a more or less relatedtopic, the vulnerability of graphs. In the first part of the thesis, Chapters 2 through 5, we concentrate on paths andcycles in weightedgraphs. A number of sufficient conditions are presentedfor graphs to contain

  19. Collaborative Robotic Instruction: A Graph Teaching Experience

    Science.gov (United States)

    Mitnik, Ruben; Recabarren, Matias; Nussbaum, Miguel; Soto, Alvaro

    2009-01-01

    Graphing is a key skill in the study of Physics. Drawing and interpreting graphs play a key role in the understanding of science, while the lack of these has proved to be a handicap and a limiting factor in the learning of scientific concepts. It has been observed that despite the amount of previous graph-working experience, students of all ages…

  20. Integral complete r-partite graphs

    NARCIS (Netherlands)

    Wang, Ligong; Li, Xueliang; Hoede, C.

    2004-01-01

    A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. It is proved that

  1. Verification Techniques for Graph Rewriting (Tutorial)

    NARCIS (Netherlands)

    Rensink, Arend; Abdulla, Parosh Aziz; Gadducci, Fabio; König, Barbara; Vafeiadis, Viktor

    This tutorial paints a high-level picture of the concepts involved in verification of graph transformation systems. We distinguish three fundamentally different application scenarios for graph rewriting: (1) as grammars (in which case we are interested in the language, or set, of terminal graphs for

  2. Graph Transformation Semantics for a QVT Language

    NARCIS (Netherlands)

    Rensink, Arend; Nederpel, Ronald; Bruni, Roberto; Varró, Dániel

    It has been claimed by many in the graph transformation community that model transformation, as understood in the context of Model Driven Architecture, can be seen as an application of graph transformation. In this paper we substantiate this claim by giving a graph transformation-based semantics to

  3. A new cluster algorithm for graphs

    NARCIS (Netherlands)

    S. van Dongen

    1998-01-01

    textabstractA new cluster algorithm for graphs called the emph{Markov Cluster algorithm ($MCL$ algorithm) is introduced. The graphs may be both weighted (with nonnegative weight) and directed. Let~$G$~be such a graph. The $MCL$ algorithm simulates flow in $G$ by first identifying $G$ in a

  4. Girth 5 graphs from relative difference sets

    DEFF Research Database (Denmark)

    Jørgensen, Leif Kjær

    We consider the problem of construction of graphs with given degree and girth 5 and as few vertices as possible. We give a construction of a family of girth 5 graphs based on relative difference sets. This family contains the smallest known graph of degree 8 and girth 5 which was constructed by G...

  5. Destroying longest cycles in graphs and digraphs

    DEFF Research Database (Denmark)

    Van Aardt, Susan A.; Burger, Alewyn P.; Dunbar, Jean E.

    2015-01-01

    In 1978, C. Thomassen proved that in any graph one can destroy all the longest cycles by deleting at most one third of the vertices. We show that for graphs with circumference k≤8 it suffices to remove at most 1/k of the vertices. The Petersen graph demonstrates that this result cannot be extended...

  6. Structure of simplicial complexes of graphs representing ...

    Indian Academy of Sciences (India)

    Abstract. Mapping time series onto graphs and the use of graph theory methods opens up the possibility to study the structure of the phase space manifolds underlying the fluctuations of a dynamical variable. Here, we go beyond the standard graph measures and analyze the higher-order structures such as triangles, ...

  7. So Many Graphs, So Little Time

    Science.gov (United States)

    Wall, Jennifer J.; Benson, Christine C.

    2009-01-01

    Interpreting graphs found in various content areas is an important skill for students, especially in light of high-stakes testing. In addition, reading and understanding graphs is an important part of numeracy, or numeric literacy, a skill necessary for informed citizenry. This article explores the different categories of graphs, provides…

  8. On topological indices for small RNA graphs.

    Science.gov (United States)

    Churkin, Alexander; Gabdank, Idan; Barash, Danny

    2012-12-01

    The secondary structure of RNAs can be represented by graphs at various resolutions. While it was shown that RNA secondary structures can be represented by coarse grain tree-graphs and meaningful topological indices can be used to distinguish between various structures, small RNAs are needed to be represented by full graphs. No meaningful topological index has yet been suggested for the analysis of such type of RNA graphs. Recalling that the second eigenvalue of the Laplacian matrix can be used to track topological changes in the case of coarse grain tree-graphs, it is plausible to assume that a topological index such as the Wiener index that represents all Laplacian eigenvalues may provide a similar guide for full graphs. However, by its original definition, the Wiener index was defined for acyclic graphs. Nevertheless, similarly to cyclic chemical graphs, small RNA graphs can be analyzed using elementary cuts, which enables the calculation of topological indices for small RNAs in an intuitive way. We show how to calculate a structural descriptor that is suitable for cyclic graphs, the Szeged index, for small RNA graphs by elementary cuts. We discuss potential uses of such a procedure that considers all eigenvalues of the associated Laplacian matrices to quantify the topology of small RNA graphs. Copyright © 2012 Elsevier Ltd. All rights reserved.

  9. 47 CFR 80.761 - Conversion graphs.

    Science.gov (United States)

    2010-10-01

    ... 47 Telecommunication 5 2010-10-01 2010-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units is...

  10. Graphs with many valencies and few eigenvalues

    NARCIS (Netherlands)

    van Dam, Edwin; Koolen, J.H.; Xia, Zheng-Jiang

    Dom de Caen posed the question whether connected graphs with three distinct eigenvalues have at most three distinct valencies. We do not answer this question, but instead construct connected graphs with four and five distinct eigenvalues and arbitrarily many distinct valencies. The graphs with four

  11. Algorithms and Data Structures for Graphs

    DEFF Research Database (Denmark)

    Rotenberg, Eva

    A graph consists of a set of vertices and a set of edges between vertices. Graphs are a popular mathematical model for road maps, communication networks, electrical circuits, social networks, disease transmission networks, job assignments, resource allocation, and more. A special class of graphs ...

  12. On 3-Chromatic Distance-Regular Graphs

    NARCIS (Netherlands)

    Blokhuis, A.; Brouwer, A.E.; Haemers, W.H.

    2006-01-01

    We give some necessary conditions for a graph to be 3-chromatic in terms of the spectrum of the adjacency matrix.For all known distance-regular graphs it is determined whether they are 3-chromatic.A start is made with the classification of 3-chromatic distance-regular graphs, and it is shown that

  13. Abstract graph-like space and vector-valued metric graphs

    OpenAIRE

    Post, Olaf

    2016-01-01

    In this note we present some abstract ideas how one can construct spaces from building blocks according to a graph. The coupling is expressed via boundary pairs, and can be applied to very different spaces such as discrete graphs, quantum graphs or graph-like manifolds. We show a spectral analysis of graph-like spaces, and consider as a special case vector-valued quantum graphs. Moreover, we provide a prototype of a convergence theorem for shrinking graph-like spaces with Dirichlet boundary c...

  14. Kirchhoff index of graphs and some graph operations

    Indian Academy of Sciences (India)

    Recently this concept has got a wide attention from different authors especially those interested ..... In this section, we pay attention to edge deletions and subdivisions and also joining vertices. Using Proposition 2.5 we ... Let H be the complete graph on x,y,z with ρxy(H ) = r , ρxz(H ) = a and ρyz(H ) = b. In K, {x,y} is a vertex ...

  15. Graph Theory and Ion and Molecular Aggregation in Aqueous Solutions.

    Science.gov (United States)

    Choi, Jun-Ho; Lee, Hochan; Choi, Hyung Ran; Cho, Minhaeng

    2018-04-20

    In molecular and cellular biology, dissolved ions and molecules have decisive effects on chemical and biological reactions, conformational stabilities, and functions of small to large biomolecules. Despite major efforts, the current state of understanding of the effects of specific ions, osmolytes, and bioprotecting sugars on the structure and dynamics of water H-bonding networks and proteins is not yet satisfactory. Recently, to gain deeper insight into this subject, we studied various aggregation processes of ions and molecules in high-concentration salt, osmolyte, and sugar solutions with time-resolved vibrational spectroscopy and molecular dynamics simulation methods. It turns out that ions (or solute molecules) have a strong propensity to self-assemble into large and polydisperse aggregates that affect both local and long-range water H-bonding structures. In particular, we have shown that graph-theoretical approaches can be used to elucidate morphological characteristics of large aggregates in various aqueous salt, osmolyte, and sugar solutions. When ion and molecular aggregates in such aqueous solutions are treated as graphs, a variety of graph-theoretical properties, such as graph spectrum, degree distribution, clustering coefficient, minimum path length, and graph entropy, can be directly calculated by considering an ensemble of configurations taken from molecular dynamics trajectories. Here we show percolating behavior exhibited by ion and molecular aggregates upon increase in solute concentration in high solute concentrations and discuss compelling evidence of the isomorphic relation between percolation transitions of ion and molecular aggregates and water H-bonding networks. We anticipate that the combination of graph theory and molecular dynamics simulation methods will be of exceptional use in achieving a deeper understanding of the fundamental physical chemistry of dissolution and in describing the interplay between the self-aggregation of solute

  16. Cofinite graphs and their profinite completions

    Directory of Open Access Journals (Sweden)

    Amrita Acharyya

    2017-10-01

    Full Text Available We generalize the idea of cofinite groups, due to B. Hartley, [2]. First we define cofinite spaces in general. Then, as a special situation, we study cofinite graphs and their uniform completions.The idea of constructing a cofinite graph starts with defining a uniform topological graph $\\Gamma$, in an appropriate fashion. We endow abstract graphs with uniformities corresponding to separating filter bases of equivalence relations with finitely many equivalence classes over $\\Gamma$. It is established that for any cofinite graph there exists a unique cofinite completion.

  17. Cycle decompositions: From graphs to continua.

    Science.gov (United States)

    Georgakopoulos, Agelos

    2012-01-30

    We generalise a fundamental graph-theoretical fact, stating that every element of the cycle space of a graph is a sum of edge-disjoint cycles, to arbitrary continua. To achieve this we replace graph cycles by topological circles, and replace the cycle space of a graph by a new homology group for continua which is a quotient of the first singular homology group [Formula: see text]. This homology seems to be particularly apt for studying spaces with infinitely generated [Formula: see text], e.g. infinite graphs or fractals.

  18. Modelling complex networks by random hierarchical graphs

    Directory of Open Access Journals (Sweden)

    M.Wróbel

    2008-06-01

    Full Text Available Numerous complex networks contain special patterns, called network motifs. These are specific subgraphs, which occur oftener than in randomized networks of Erdős-Rényi type. We choose one of them, the triangle, and build a family of random hierarchical graphs, being Sierpiński gasket-based graphs with random "decorations". We calculate the important characteristics of these graphs - average degree, average shortest path length, small-world graph family characteristics. They depend on probability of decorations. We analyze the Ising model on our graphs and describe its critical properties using a renormalization-group technique.

  19. Subsampling for graph power spectrum estimation

    KAUST Repository

    Chepuri, Sundeep Prabhakar

    2016-10-06

    In this paper we focus on subsampling stationary random signals that reside on the vertices of undirected graphs. Second-order stationary graph signals are obtained by filtering white noise and they admit a well-defined power spectrum. Estimating the graph power spectrum forms a central component of stationary graph signal processing and related inference tasks. We show that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the power spectrum of the graph signal from the subsampled observations, without any spectral priors. In addition, a near-optimal greedy algorithm is developed to design the subsampling scheme.

  20. Cosmological coevolution of Yang-Mills fields and perfect fluids

    International Nuclear Information System (INIS)

    Barrow, John D.; Jin, Yoshida; Maeda, Kei-ichi

    2005-01-01

    We study the coevolution of Yang-Mills fields and perfect fluids in Bianchi type I universes. We investigate numerically the evolution of the universe and the Yang-Mills fields during the radiation and dust eras of a universe that is almost isotropic. The Yang-Mills field undergoes small amplitude chaotic oscillations, as do the three expansion scale factors which are also displayed by the expansion scale factors of the universe. The results of the numerical simulations are interpreted analytically and compared with past studies of the cosmological evolution of magnetic fields in radiation and dust universes. We find that, whereas magnetic universes are strongly constrained by the microwave background anisotropy, Yang-Mills universes are principally constrained by primordial nucleosynthesis but the bound is comparatively weak with Ω YM rad

  1. The oil crisis: China, the perfect scapegoat

    International Nuclear Information System (INIS)

    Lafargue, F.

    2008-01-01

    The Western economies have been confronted with rising oil prices for the past five years. Political instability in the Middle East, social unrest in Nigeria and Hugo Chavez nationalizations all reinforce our dread of a shortage. This oil crisis is often presented as the consequence of the rapid industrialization of India and China. As so often in Europe, we try to explain our own difficulties by transforming China (and to a lesser extent, India) into the perfect scapegoat; but what is the reality? (author)

  2. Dynamic diffraction of neutrons on perfect crystals

    International Nuclear Information System (INIS)

    Abov, Yu.G.; Tyulyusov, A.N.; Elyutin, N.O.

    2002-01-01

    Theory and experimental results are presented for the phenomena observed in the interaction of a thermal neutron beam with a regular periodic system of nuclei, which constitutes a perfect crystal. Recent studies in this field resulted in the appearance of new trends in the neutron optics, such as neutron interferometry and topography. High angular- and energy-resolution neutron crystal spectrometers were designed and manufactured for the investigation of small-angle and diffractive scattering. Passable new theoretical description of neutron dynamic diffraction and new experiments with neutron beams are discussed [ru

  3. Dynamic diffraction of neutrons on perfect crystals

    CERN Document Server

    Abov, Y G; Elyutin, N O

    2002-01-01

    Theory and experimental results are presented for the phenomena observed in the interaction of a thermal neutron beam with a regular periodic system of nuclei, which constitutes a perfect crystal. Recent studies in this field resulted in the appearance of new trends in the neutron optics, such as neutron interferometry and topography. High angular- and energy-resolution neutron crystal spectrometers were designed and manufactured for the investigation of small-angle and diffractive scattering. Passable new theoretical description of neutron dynamic diffraction and new experiments with neutron beams are discussed

  4. The perfection of loss-free counting

    International Nuclear Information System (INIS)

    Westphal, G.P.; Lemmel, H.

    2008-01-01

    Pileup losses in nuclear pulse spectrometry also depend on energy as lower energies produce narrower pulses which in turn have better chances to avoid pulse pileup. Consequently, in our present system individual energy-dependent pileup correction factors are calculated for all events, making it what very probably may be called the first perfect implementation of Loss-Free Counting. Temporal response and quantitative performance of the new system are tested over the whole range of counting rates (up to 106 c/s) and counting losses (up to 99%) by means of short-lived isomeric transitions and a fast rabbit system. (author)

  5. Subgame Perfect Punishment for Repeat Offenders

    OpenAIRE

    Winand Emons

    2002-01-01

    First we show that for wealth-constrained agents who may commit an act twice the optimal sanctions are the offender's entire wealth for the first and zero for the second crime. Then we ask the question whether this decreasing sanction scheme is subgame perfect (time consistent), i.e., does a rent-seeking government stick to this sanction scheme after the first crime has occurred. If the benefit and/or the harm from the crime are not too large, this is indeed the case; otherwise, equal sanctio...

  6. Constrained Graph Optimization: Interdiction and Preservation Problems

    Energy Technology Data Exchange (ETDEWEB)

    Schild, Aaron V [Los Alamos National Laboratory

    2012-07-30

    The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.

  7. Using Behavior Over Time Graphs to Spur Systems Thinking Among Public Health Practitioners.

    Science.gov (United States)

    Calancie, Larissa; Anderson, Seri; Branscomb, Jane; Apostolico, Alexsandra A; Lich, Kristen Hassmiller

    2018-02-01

    Public health practitioners can use Behavior Over Time (BOT) graphs to spur discussion and systems thinking around complex challenges. Multiple large systems, such as health care, the economy, and education, affect chronic disease rates in the United States. System thinking tools can build public health practitioners' capacity to understand these systems and collaborate within and across sectors to improve population health. BOT graphs show a variable, or variables (y axis) over time (x axis). Although analyzing trends is not new to public health, drawing BOT graphs, annotating the events and systemic forces that are likely to influence the depicted trends, and then discussing the graphs in a diverse group provides an opportunity for public health practitioners to hear each other's perspectives and creates a more holistic understanding of the key factors that contribute to a trend. We describe how BOT graphs are used in public health, how they can be used to generate group discussion, and how this process can advance systems-level thinking. Then we describe how BOT graphs were used with groups of maternal and child health (MCH) practitioners and partners (N = 101) during a training session to advance their thinking about MCH challenges. Eighty-six percent of the 84 participants who completed an evaluation agreed or strongly agreed that they would use this BOT graph process to engage stakeholders in their home states and jurisdictions. The BOT graph process we describe can be applied to a variety of public health issues and used by practitioners, stakeholders, and researchers.

  8. On a programming language for graph algorithms

    Science.gov (United States)

    Rheinboldt, W. C.; Basili, V. R.; Mesztenyi, C. K.

    1971-01-01

    An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.

  9. Modes of Convergence for Term Graph Rewriting

    DEFF Research Database (Denmark)

    Bahr, Patrick

    2012-01-01

    Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent. However, this endeavour is impaired by the lack of an appropriate...... counterpart of infinitary rewriting on the side of term graphs. We aim to fill this gap by devising two modes of convergence based on a partial order respectively a metric on term graphs. The thus obtained structures generalise corresponding modes of convergence that are usually studied in infinitary term...... rewriting. We argue that this yields a common framework in which both term rewriting and term graph rewriting can be studied. In order to substantiate our claim, we compare convergence on term graphs and on terms. In particular, we show that the modes of convergence on term graphs are conservative...

  10. Modes of Convergence for Term Graph Rewriting

    DEFF Research Database (Denmark)

    Bahr, Patrick

    2011-01-01

    Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent. However, this endeavour is impaired by the lack of an appropriate...... counterpart of infinitary rewriting on the side of term graphs. We aim to fill this gap by devising two modes of convergence based on a partial order resp. a metric on term graphs. The thus obtained structures generalise corresponding modes of convergence that are usually studied in infinitary term rewriting....... We argue that this yields a common framework in which both term rewriting and term graph rewriting can be studied. In order to substantiate our claim, we compare convergence on term graphs and on terms. In particular, we show that the resulting infinitary calculi of term graph rewriting exhibit...

  11. On the centrality of some graphs

    Directory of Open Access Journals (Sweden)

    Vecdi Aytac

    2017-10-01

    Full Text Available A central issue in the analysis of complex networks is the assessment of their stability and vulnerability. A variety of measures have been proposed in the literature to quantify the stability of networks and a number of graph-theoretic parameters have been used to derive formulas for calculating network reliability. Different measures for graph vulnerability have been introduced so far to study different aspects of the graph behavior after removal of vertices or links such as connectivity, toughness, scattering number, binding number, residual closeness and integrity. In this paper, we consider betweenness centrality of a graph. Betweenness centrality of a vertex of a graph is portion of the shortest paths all pairs of vertices passing through a given vertex. In this paper, we obtain exact values for betweenness centrality for some wheel related graphs namely gear, helm, sunflower and friendship graphs.

  12. A kaleidoscopic view of graph colorings

    CERN Document Server

    Zhang, Ping

    2016-01-01

    This book describes kaleidoscopic topics that have developed in the area of graph colorings. Unifying current material on graph coloring, this book describes current information on vertex and edge colorings in graph theory, including harmonious colorings, majestic colorings, kaleidoscopic colorings and binomial colorings. Recently there have been a number of breakthroughs in vertex colorings that give rise to other colorings in a graph, such as graceful labelings of graphs that have been reconsidered under the language of colorings. The topics presented in this book include sample detailed proofs and illustrations, which depicts elements that are often overlooked. This book is ideal for graduate students and researchers in graph theory, as it covers a broad range of topics and makes connections between recent developments and well-known areas in graph theory.

  13. Software for Graph Analysis and Visualization

    Directory of Open Access Journals (Sweden)

    M. I. Kolomeychenko

    2014-01-01

    Full Text Available This paper describes the software for graph storage, analysis and visualization. The article presents a comparative analysis of existing software for analysis and visualization of graphs, describes the overall architecture of application and basic principles of construction and operation of the main modules. Furthermore, a description of the developed graph storage oriented to storage and processing of large-scale graphs is presented. The developed algorithm for finding communities and implemented algorithms of autolayouts of graphs are the main functionality of the product. The main advantage of the developed software is high speed processing of large size networks (up to millions of nodes and links. Moreover, the proposed graph storage architecture is unique and has no analogues. The developed approaches and algorithms are optimized for operating with big graphs and have high productivity.

  14. Fibonacci number of the tadpole graph

    Directory of Open Access Journals (Sweden)

    Joe DeMaio

    2014-10-01

    Full Text Available In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G to be the number of independent sets of the graph G. They did so since the Fibonacci number of the path graph Pn is the Fibonacci number F(n+2 and the Fibonacci number of the cycle graph Cn is the Lucas number Ln. The tadpole graph Tn,k is the graph created by concatenating Cn and Pk with an edge from any vertex of Cn to a pendant of Pk for integers n=3 and k=0. This paper establishes formulae and identities for the Fibonacci number of the tadpole graph via algebraic and combinatorial methods.

  15. Triangle Counting in Dynamic Graph Streams

    DEFF Research Database (Denmark)

    Bulteau, Laurent; Froese, Vincent; Pagh, Rasmus

    2015-01-01

    Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However......, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions...... for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach...

  16. On the Contribution of Slovenian Linguistics to the History of the Ancient Greek Perfect

    Directory of Open Access Journals (Sweden)

    Jerneja Kavčič

    2010-12-01

    Full Text Available An important contribution to the history of the Ancient Greek perfect is the study of Erika Mihevc-Gabrovec, The Disappearance of the Perfect in Late Greek (La disparition du parfait dans le grec de la basse époque. In terms of theory and content, her study continues the work of Pierre Chantraine, but somewhat diverges from her predecessor’s views on the issue of the merger between the aorist and the perfect, identifying examples of the use of the perfect even in an – according to Pierre Chantraine – relatively late period.  Some years after the publication of Erika Mihevc-Gabrovec’s book, the question of when the aorist and the perfect may have merged was raised again, to be addressed by McKay in a number of articles. Today, the views on the subject are strongly divided.   As argued by the author of this paper, one of the setbacks in examining the merger between the aorist and the perfect concerns the methodology, since researchers have tended to rely exclusively on their sense of language. A possible new approach is offered in the framework of the Slovenian theory of Natural Syntax, which has from the start paid considerable attention to English sentences of the I believe her to be intelligent type. The paper describes similar sentences in New Testament Greek, terming them “sentences of the λέγουσινἀνάστασινμὴεἶναι type”. In New Testament Greek, they display a tendency to use the present infinitive of stative verbs; relatively frequent is also the perfect infinitive (of non-stative verbs, while, as already noted in other studies, these sentences – at least in New Testament Greek – avoid the aorist infinitive. Such sentences thus bear witness to the fact that the aorist and the perfect were not fully interchangeable in New Testament Greek; the status of the aorist and perfect infinitives in sentences of the λέγουσινἀνάστασινμὴεἶναι type should also be taken into

  17. Graph Embedded Extreme Learning Machine.

    Science.gov (United States)

    Iosifidis, Alexandros; Tefas, Anastasios; Pitas, Ioannis

    2016-01-01

    In this paper, we propose a novel extension of the extreme learning machine (ELM) algorithm for single-hidden layer feedforward neural network training that is able to incorporate subspace learning (SL) criteria on the optimization process followed for the calculation of the network's output weights. The proposed graph embedded ELM (GEELM) algorithm is able to naturally exploit both intrinsic and penalty SL criteria that have been (or will be) designed under the graph embedding framework. In addition, we extend the proposed GEELM algorithm in order to be able to exploit SL criteria in arbitrary (even infinite) dimensional ELM spaces. We evaluate the proposed approach on eight standard classification problems and nine publicly available datasets designed for three problems related to human behavior analysis, i.e., the recognition of human face, facial expression, and activity. Experimental results denote the effectiveness of the proposed approach, since it outperforms other ELM-based classification schemes in all the cases.

  18. The optimal graph partitioning problem

    DEFF Research Database (Denmark)

    Sørensen, Michael Malmros; Holm, Søren

    1993-01-01

    In this paper we consider the problem of partitioning the set of nodes in a graph in at most p classes, such that the sum of node weights in any class is not greater than the class capacity b, and such that the sum of edge weights, for edges connecting nodes in the same class, is maximal. This pr......In this paper we consider the problem of partitioning the set of nodes in a graph in at most p classes, such that the sum of node weights in any class is not greater than the class capacity b, and such that the sum of edge weights, for edges connecting nodes in the same class, is maximal...

  19. Significance evaluation in factor graphs

    DEFF Research Database (Denmark)

    Madsen, Tobias; Hobolth, Asger; Jensen, Jens Ledet

    2017-01-01

    in genomics and the multiple-testing issues accompanying them, accurate significance evaluation is of great importance. We here address the problem of evaluating statistical significance of observations from factor graph models. Results Two novel numerical approximations for evaluation of statistical...... significance are presented. First a method using importance sampling. Second a saddlepoint approximation based method. We develop algorithms to efficiently compute the approximations and compare them to naive sampling and the normal approximation. The individual merits of the methods are analysed both from....... Conclusions The applicability of saddlepoint approximation and importance sampling is demonstrated on known models in the factor graph framework. Using the two methods we can substantially improve computational cost without compromising accuracy. This contribution allows analyses of large datasets...

  20. 3-biplacement of bipartite graphs

    Directory of Open Access Journals (Sweden)

    Lech Adamus

    2008-01-01

    Full Text Available Let \\(G=(L,R;E\\ be a bipartite graph with color classes \\(L\\ and \\(R\\ and edge set \\(E\\. A set of two bijections \\(\\{\\varphi_1 , \\varphi_2\\}\\, \\(\\varphi_1 , \\varphi_2 :L \\cup R \\to L \\cup R\\, is said to be a \\(3\\-biplacement of \\(G\\ if \\(\\varphi_1(L= \\varphi_2(L = L\\ and \\(E \\cap \\varphi_1^*(E=\\emptyset\\, \\(E \\cap \\varphi_2^*(E=\\emptyset\\, \\(\\varphi_1^*(E \\cap \\varphi_2^*(E=\\emptyset\\, where \\(\\varphi_1^*\\, \\(\\varphi_2^*\\ are the maps defined on \\(E\\, induced by \\(\\varphi_1\\, \\(\\varphi_2\\, respectively. We prove that if \\(|L| = p\\, \\(|R| = q\\, \\(3 \\leq p \\leq q\\, then every graph \\(G=(L,R;E\\ of size at most \\(p\\ has a \\(3\\-biplacement.

  1. Reachability Games on Automatic Graphs

    Science.gov (United States)

    Neider, Daniel

    In this work we study two-person reachability games on finite and infinite automatic graphs. For the finite case we empirically show that automatic game encodings are competitive to well-known symbolic techniques such as BDDs, SAT and QBF formulas. For the infinite case we present a novel algorithm utilizing algorithmic learning techniques, which allows to solve huge classes of automatic reachability games.

  2. Decomposing a graph into bistars

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2013-01-01

    Bárat and the present author conjectured that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT-edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition, that is, a decomposition of the edge set into trees each of which...

  3. Parallel External Memory Graph Algorithms

    DEFF Research Database (Denmark)

    Arge, Lars Allan; Goodrich, Michael T.; Sitchinava, Nodari

    2010-01-01

    In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one o f the private-cache chip multiprocessor (CMP) models. We study the fundamental problem of list ranking which leads to efficient solutions to problems on trees, such as computing lowest...... an optimal speedup of ¿(P) in parallel I/O complexity and parallel computation time, compared to the single-processor external memory counterparts....

  4. Quantum information processing with graph states

    International Nuclear Information System (INIS)

    Schlingemann, Dirk-Michael

    2005-04-01

    Graph states are multiparticle states which are associated with graphs. Each vertex of the graph corresponds to a single system or particle. The links describe quantum correlations (entanglement) between pairs of connected particles. Graph states were initiated independently by two research groups: On the one hand, graph states were introduced by Briegel and Raussendorf as a resource for a new model of one-way quantum computing, where algorithms are implemented by a sequence of measurements at single particles. On the other hand, graph states were developed by the author of this thesis and ReinhardWerner in Braunschweig, as a tool to build quantum error correcting codes, called graph codes. The connection between the two approaches was fully realized in close cooperation of both research groups. This habilitation thesis provides a survey of the theory of graph codes, focussing mainly, but not exclusively on the author's own research work. We present the theoretical and mathematical background for the analysis of graph codes. The concept of one-way quantum computing for general graph states is discussed. We explicitly show how to realize the encoding and decoding device of a graph code on a one-way quantum computer. This kind of implementation is to be seen as a mathematical description of a quantum memory device. In addition to that, we investigate interaction processes, which enable the creation of graph states on very large systems. Particular graph states can be created, for instance, by an Ising type interaction between next neighbor particles which sits at the points of an infinitely extended cubic lattice. Based on the theory of quantum cellular automata, we give a constructive characterization of general interactions which create a translationally invariant graph state. (orig.)

  5. Topological structure of dictionary graphs

    International Nuclear Information System (INIS)

    Fuks, Henryk; Krzeminski, Mark

    2009-01-01

    We investigate the topological structure of the subgraphs of dictionary graphs constructed from WordNet and Moby thesaurus data. In the process of learning a foreign language, the learner knows only a subset of all words of the language, corresponding to a subgraph of a dictionary graph. When this subgraph grows with time, its topological properties change. We introduce the notion of the pseudocore and argue that the growth of the vocabulary roughly follows decreasing pseudocore numbers-that is, one first learns words with a high pseudocore number followed by smaller pseudocores. We also propose an alternative strategy for vocabulary growth, involving decreasing core numbers as opposed to pseudocore numbers. We find that as the core or pseudocore grows in size, the clustering coefficient first decreases, then reaches a minimum and starts increasing again. The minimum occurs when the vocabulary reaches a size between 10 3 and 10 4 . A simple model exhibiting similar behavior is proposed. The model is based on a generalized geometric random graph. Possible implications for language learning are discussed.

  6. Dynkin graphs and quadrilateral singularities

    CERN Document Server

    Urabe, Tohsuke

    1993-01-01

    The study of hypersurface quadrilateral singularities can be reduced to the study of elliptic K3 surfaces with a singular fiber of type I * 0 (superscript *, subscript 0), and therefore these notes consider, besides the topics of the title, such K3 surfaces too. The combinations of rational double points that can occur on fibers in the semi-universal deformations of quadrilateral singularities are examined, to show that the possible combinations can be described by a certain law from the viewpoint of Dynkin graphs. This is equivalent to saying that the possible combinations of singular fibers in elliptic K3 surfaces with a singular fiber of type I * 0 (superscript *, subscript 0) can be described by a certain law using classical Dynkin graphs appearing in the theory of semi-simple Lie groups. Further, a similar description for thecombination of singularities on plane sextic curves is given. Standard knowledge of algebraic geometry at the level of graduate students is expected. A new method based on graphs wil...

  7. Apnea of prematurity--perfect storm.

    Science.gov (United States)

    Di Fiore, Juliann M; Martin, Richard J; Gauda, Estelle B

    2013-11-01

    With increased survival of preterm infants as young as 23 weeks gestation, maintaining adequate respiration and corresponding oxygenation represents a clinical challenge in this unique patient cohort. Respiratory instability characterized by apnea and periodic breathing occurs in premature infants because of immature development of the respiratory network. While short respiratory pauses and apnea may be of minimal consequence if oxygenation is maintained, they can be problematic if accompanied by chronic intermittent hypoxemia. Underdevelopment of the lung and the resultant lung injury that occurs in this population concurrent with respiratory instability creates the perfect storm leading to frequent episodes of profound and recurrent hypoxemia. Chronic intermittent hypoxemia contributes to the immediate and long term co-morbidities that occur in this population. In this review we discuss the pathophysiology leading to the perfect storm, diagnostic assessment of breathing instability in this unique population and therapeutic interventions that aim to stabilize breathing without contributing to tissue injury. Copyright © 2013. Published by Elsevier B.V.

  8. On Partial Charge Transfer Processes in Multiparticle Systems on Graphs

    Directory of Open Access Journals (Sweden)

    Victor Chulaevsky

    2014-01-01

    Full Text Available We assess the probability of resonances between sufficiently distant states of an N-particle disordered quantum system in a combinatorial graph Z. In the N-particle configuration space, there are arbitrarily distant pairs of configurations giving rise to pairs of local (random Hamiltonians which are strongly coupled, so that the eigenvalue concentration (EVC bounds are difficult to obtain. We extend to any number of particles the efficient EVC bounds, obtained earlier for the 2-particle systems.

  9. Charged perfect fluid tori in strong central gravitational and dipolar magnetic fields

    Czech Academy of Sciences Publication Activity Database

    Kovář, J.; Slaný, P.; Cremaschini, C.; Stuchlík, Z.; Karas, Vladimír; Trova, Audrey

    2016-01-01

    Roč. 93, June (2016), 124055/1-124055/20 ISSN 1550-7998 R&D Projects: GA ČR GB14-37086G; GA MŠk(CZ) LH14049 Grant - others:GA ČR(CZ) GP14-07753P Institutional support: RVO:67985815 Keywords : black holes * accretion discscretion discs Subject RIV: BN - Astronomy, Celestial Mechanics, Astrophysics Impact factor: 4.643, year: 2014

  10. Innovative Writing Instruction: Practice Makes Perfect! Realizing Classrooms as "Landscapes of Learning," Not Places of Perfection

    Science.gov (United States)

    Ozier, Lance

    2011-01-01

    Pressure for students to produce writing perfection in the classroom often eclipses the emphasis placed on the need for students to practice writing. Occasions for students to choose, challenge, and reflect--to actually risk risking--are too often absent from conversations among students and teachers in countless English classrooms. Tom Romano…

  11. A perfect launch of Space Shuttle Discovery

    Science.gov (United States)

    2000-01-01

    Space Shuttle Discovery lifts off Launch Pad 39A against a backdrop of xenon lights (just above the orbiter' nose and at left). On the Mobile Launcher Platform beneath, water begins flooding the area for flame and sound control. The perfect on- time liftoff occurred at 7:17 p.m. EDT, sending a crew of seven on the 100th launch in the history of the Shuttle program. Discovery carries a payload that includes the Integrated Truss Structure Z-1, first of 10 trusses that will form the backbone of the Space Station, and the third Pressurized Mating Adapter that will provide a Shuttle docking port for solar array installation on the sixth Station flight and Lab installation on the seventh Station flight. Discovery's landing is expected Oct. 22 at 2:10 p.m. EDT.

  12. Electromagnetic Detection of a Perfect Carpet Cloak

    Science.gov (United States)

    Shi, Xihang; Gao, Fei; Lin, Xiao; Zhang, Baile

    2015-05-01

    It has been shown that a spherical invisibility cloak originally proposed by Pendry et al. can be electromagnetically detected by shooting a charged particle through it, whose underlying mechanism stems from the asymmetry of transformation optics applied to motions of photons and charges [PRL 103, 243901 (2009)]. However, the conceptual three-dimensional invisibility cloak that exactly follows specifications of transformation optics is formidably difficult to implement, while the simplified cylindrical cloak that has been experimentally realized is inherently visible. On the other hand, the recent carpet cloak model has acquired remarkable experimental development, including a recently demonstrated full-parameter carpet cloak without any approximation in the required constitutive parameters. In this paper, we numerically investigate the electromagnetic radiation from a charged particle passing through a perfect carpet cloak and propose an experimentally verifiable model to demonstrate symmetry breaking of transformation optics.

  13. A perfect launch viewed across Banana Creek

    Science.gov (United States)

    2000-01-01

    Billows of smoke and steam surround Space Shuttle Discovery as it lifts off from Launch Pad 39A on mission STS-92 to the International Space Station. The perfect on-time liftoff occurred at 7:17 p.m. EDT, sending a crew of seven on the 100th launch in the history of the Shuttle program. Discovery carries a payload that includes the Integrated Truss Structure Z-1, first of 10 trusses that will form the backbone of the Space Station, and the third Pressurized Mating Adapter that will provide a Shuttle docking port for solar array installation on the sixth Station flight and Lab installation on the seventh Station flight. Discovery's landing is expected Oct. 22 at 2:10 p.m. EDT.

  14. Field theory of the Eulerian perfect fluid

    Science.gov (United States)

    Ariki, Taketo; Morales, Pablo A.

    2018-01-01

    The Eulerian perfect-fluid theory is reformulated from its action principle in a pure field-theoretic manner. Conservation of the convective current is no longer imposed by Lin’s constraints, but rather adopted as the central idea of the theory. Our formulation, for the first time, successfully reduces redundant degrees of freedom promoting one half of the Clebsch variables to true dynamical fields. Interactions on these fields allow for the exchange of the convective current of quantities such as mass and charge, which are uniformly understood as the breaking of the underlying symmetry of the force-free fluid. The Clebsch fields play the essential role of exchanging angular momentum with the force field producing vorticity.

  15. The surveyors' quest for perfect alignment

    CERN Multimedia

    2003-01-01

    Photogrammetry of a CMS endcap and part of the hadronic calorimeter.The structure was covered with targets photographed by digital cameras. Perfect alignment.... Although CERN's surveyors do not claim to achieve it, they are constantly striving for it and deploy all necessary means to come as close as they can. In their highly specialised field of large-scale metrology, the solution lies in geodesy and photogrammetry, both of which are based on increasingly sophisticated instruments and systems. In civil engineering, these techniques are used for non-destructive inspection of bridges, dams and other structures, while industrial applications include dimensional verification and deformation measurement in large mechanical assemblies. The same techniques also come into play for the metrology of research tools such as large telescopes and of course, particle accelerators. Particle physics laboratories are especially demanding customers, and CERN has often asked for the impossible. As a result, the alignment metro...

  16. Theory of metasurface based perfect absorbers

    Science.gov (United States)

    Alaee, Rasoul; Albooyeh, Mohammad; Rockstuhl, Carsten

    2017-12-01

    Based on an analytic approach, we present a theoretical review on the absorption, scattering, and extinction of both dipole scatterers and regular arrays composed of such scatterers i.e. metasurfaces. Besides offering a tutorial by outlining the maximum absorption limit for electrically/magnetically resonant dipole particles/metasurfaces, we give an educative analytical approach to their analysis. Moreover, we put forward the analysis of two known alternatives in providing perfect absorbers out of electrically and or magnetically resonant metasurfaces; one is based on the simultaneous presence of both electric and magnetic responses in so called Huygens metasurfaces while the other is established upon the presence of a back reflector in so called Salisbury absorbers. Our work is supported by several numerical examples to clarify the discussions in each stage.

  17. Three Syntactic Theories for Combinatory Graph Reduction

    DEFF Research Database (Denmark)

    Danvy, Olivier; Zerny, Ian

    2011-01-01

    We present a purely syntactic theory of graph reduction for the canonical combinators S, K, and I, where graph vertices are represented with evaluation contexts and let expressions. We express this syntactic theory as a reduction semantics, which we refocus into the first storeless abstract machine...... for combinatory graph reduction, which we refunctionalize into the first storeless natural semantics for combinatory graph reduction.We then factor out the introduction of let expressions to denote as many graph vertices as possible upfront instead of on demand, resulting in a second syntactic theory, this one...... of term graphs in the sense of Barendregt et al. The corresponding storeless abstract machine and natural semantics follow mutatis mutandis. We then interpret let expressions as operations over a global store (thus shifting, in Strachey's words, from denotable entities to storable entities), resulting...

  18. Chemical Graph Transformation with Stereo-Information

    DEFF Research Database (Denmark)

    Andersen, Jakob Lykke; Flamm, Christoph; Merkle, Daniel

    2017-01-01

    Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms and their neighbo......Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms...... and their neighbours in space. Stereoisomers of chemical compounds thus cannot be distinguished, even though their chemical activity may differ substantially. In this contribution we propose an extended chemical graph transformation system with attributes that encode information about local geometry. The modelling...... of graph transformation, but we here propose a framework that also allows for partially specified stereoinformation. While there are several stereochemical configurations to be considered, we focus here on the tetrahedral molecular shape, and suggest general principles for how to treat all other chemically...

  19. Double-Critical Graphs and Complete Minors

    DEFF Research Database (Denmark)

    Kawarabayashi, Ken-ichi; Pedersen, Anders Sune; Toft, Bjarne

    2010-01-01

      A connected $k$-chromatic graph $G$ is double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k-2)$-colourable. The only known double-critical $k$-chromatic graph is the complete $k$-graph $K_k$. The conjecture that there are no other double-critical graphs is a special case...... of a conjecture from 1966, due to Erd\\H{o}s and Lov\\'asz.  The conjecture has been verified for $k \\leq 5$.  We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is $6$-connected and has $K_k$ as a minor. Udgivelsesdato: 07.06....

  20. Alliances and Bisection Width for Planar Graphs

    DEFF Research Database (Denmark)

    Olsen, Martin; Revsbæk, Morten

    2013-01-01

    An alliance in a graph is a set of vertices (allies) such that each vertex in the alliance has at least as many allies (counting the vertex itself) as non-allies in its neighborhood of the graph. We show that any planar graph with minimum degree at least 4 can be split into two alliances...... in polynomial time. We base this on a proof of an upper bound of n on the bisection width for 4-connected planar graphs with an odd number of vertices. This improves a recently published n + 1 upper bound on the bisection width of planar graphs without separating triangles and supports the folklore conjecture...... that a general upper bound of n exists for the bisection width of planar graphs....

  1. Fast Generation of Sparse Random Kernel Graphs.

    Science.gov (United States)

    Hagberg, Aric; Lemons, Nathan

    2015-01-01

    The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most (n(logn)2). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.

  2. 2-domination number of generalized Petersen graphs

    Indian Academy of Sciences (India)

    35

    2Department of Computer Science, Yazd University, Yazd, Iran. Abstract. Let G = (V,E) be a graph. A subset S ⊆ V is a k-dominating set of. G if each vertex ... on the area of domination in graphs and its applications we refer the reader to [6, 7]. The generalized Petersen graph P(n, k)=(V,E) is defined as follows: V = {v1,v2,...

  3. On path hypercompositions in graphs and automata

    Directory of Open Access Journals (Sweden)

    Massouros Christos G.

    2016-01-01

    Full Text Available The paths in graphs define hypercompositions in the set of their vertices and therefore it is feasible to associate hypercompositional structures to each graph. Similarly, the strings of letters from their alphabet, define hypercompositions in the automata, which in turn define the associated hypergroups to the automata. The study of the associated hypercompositional structures gives results in both, graphs and automata theory.

  4. Visibility graphs and landscape visibility analysis

    OpenAIRE

    O Sullivan, D.; Turner, A.

    2001-01-01

    Visibility analysis based on viewsheds is one of the most frequently used GIS analysis tools. In this paper we present an approach to visibility analysis based on the visibility graph. A visibility graph records the pattern of mutual visibility relations in a landscape, and provides a convenient way of storing and further analysing the results of multiple viewshed analyses for a particular landscape region. We describe how a visibility graph may be calculated for a landscape. We then give exa...

  5. Steiner Distance in Graphs--A Survey

    OpenAIRE

    Mao, Yaping

    2017-01-01

    For a connected graph $G$ of order at least $2$ and $S\\subseteq V(G)$, the \\emph{Steiner distance} $d_G(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. In this paper, we summarize the known results on the Steiner distance parameters, including Steiner distance, Steiner diameter, Steiner center, Steiner median, Steiner interval, Steiner distance hereditary graph, Steiner distance stable graph, average Steiner distance, and Steiner ...

  6. Wormholes in virtual space: From cognitive maps to cognitive graphs.

    Science.gov (United States)

    Warren, William H; Rothman, Daniel B; Schnapp, Benjamin H; Ericson, Jonathan D

    2017-09-01

    Humans and other animals build up spatial knowledge of the environment on the basis of visual information and path integration. We compare three hypotheses about the geometry of this knowledge of navigation space: (a) 'cognitive map' with metric Euclidean structure and a consistent coordinate system, (b) 'topological graph' or network of paths between places, and (c) 'labelled graph' incorporating local metric information about path lengths and junction angles. In two experiments, participants walked in a non-Euclidean environment, a virtual hedge maze containing two 'wormholes' that visually rotated and teleported them between locations. During training, they learned the metric locations of eight target objects from a 'home' location, which were visible individually. During testing, shorter wormhole routes to a target were preferred, and novel shortcuts were directional, contrary to the topological hypothesis. Shortcuts were strongly biased by the wormholes, with mean constant errors of 37° and 41° (45° expected), revealing violations of the metric postulates in spatial knowledge. In addition, shortcuts to targets near wormholes shifted relative to flanking targets, revealing 'rips' (86% of cases), 'folds' (91%), and ordinal reversals (66%) in spatial knowledge. Moreover, participants were completely unaware of these geometric inconsistencies, reflecting a surprising insensitivity to Euclidean structure. The probability of the shortcut data under the Euclidean map model and labelled graph model indicated decisive support for the latter (BF GM >100). We conclude that knowledge of navigation space is best characterized by a labelled graph, in which local metric information is approximate, geometrically inconsistent, and not embedded in a common coordinate system. This class of 'cognitive graph' models supports route finding, novel detours, and rough shortcuts, and has the potential to unify a range of data on spatial navigation. Copyright © 2017 Elsevier B

  7. EmptyHeaded: A Relational Engine for Graph Processing.

    Science.gov (United States)

    Aberger, Christopher R; Tu, Susan; Olukotun, Kunle; Ré, Christopher

    2016-01-01

    There are two types of high-performance graph processing engines: low- and high-level engines. Low-level engines (Galois, PowerGraph, Snap) provide optimized data structures and computation models but require users to write low-level imperative code, hence ensuring that efficiency is the burden of the user. In high-level engines, users write in query languages like datalog (SociaLite) or SQL (Grail). High-level engines are easier to use but are orders of magnitude slower than the low-level graph engines. We present EmptyHeaded, a high-level engine that supports a rich datalog-like query language and achieves performance comparable to that of low-level engines. At the core of EmptyHeaded's design is a new class of join algorithms that satisfy strong theoretical guarantees but have thus far not achieved performance comparable to that of specialized graph processing engines. To achieve high performance, EmptyHeaded introduces a new join engine architecture, including a novel query optimizer and data layouts that leverage single-instruction multiple data (SIMD) parallelism. With this architecture, EmptyHeaded outperforms high-level approaches by up to three orders of magnitude on graph pattern queries, PageRank, and Single-Source Shortest Paths (SSSP) and is an order of magnitude faster than many low-level baselines. We validate that EmptyHeaded competes with the best-of-breed low-level engine (Galois), achieving comparable performance on PageRank and at most 3× worse performance on SSSP.

  8. The Harary index of a graph

    CERN Document Server

    Xu, Kexiang; Trinajstić, Nenad

    2015-01-01

    This is the first book to focus on the topological index, the Harary index, of a graph, including its mathematical properties, chemical applications and some related and attractive open problems. This book is dedicated to Professor Frank Harary (1921—2005), the grandmaster of graph theory and its applications. It has be written by experts in the field of graph theory and its applications. For a connected graph G, as an important distance-based topological index, the Harary index H(G) is defined as the sum of the reciprocals of the distance between any two unordered vertices of the graph G. In this book, the authors report on the newest results on the Harary index of a graph. These results mainly concern external graphs with respect to the Harary index; the relations to other topological indices; its properties and applications to pure graph theory and chemical graph theory; and two significant variants, i.e., additively and multiplicatively weighted Harary indices. In the last chapter, we present a number o...

  9. Interactive Graph Layout of a Million Nodes

    Directory of Open Access Journals (Sweden)

    Peng Mi

    2016-12-01

    Full Text Available Sensemaking of large graphs, specifically those with millions of nodes, is a crucial task in many fields. Automatic graph layout algorithms, augmented with real-time human-in-the-loop interaction, can potentially support sensemaking of large graphs. However, designing interactive algorithms to achieve this is challenging. In this paper, we tackle the scalability problem of interactive layout of large graphs, and contribute a new GPU-based force-directed layout algorithm that exploits graph topology. This algorithm can interactively layout graphs with millions of nodes, and support real-time interaction to explore alternative graph layouts. Users can directly manipulate the layout of vertices in a force-directed fashion. The complexity of traditional repulsive force computation is reduced by approximating calculations based on the hierarchical structure of multi-level clustered graphs. We evaluate the algorithm performance, and demonstrate human-in-the-loop layout in two sensemaking case studies. Moreover, we summarize lessons learned for designing interactive large graph layout algorithms on the GPU.

  10. Evolutionary Games of Multiplayer Cooperation on Graphs

    Science.gov (United States)

    Arranz, Jordi; Traulsen, Arne

    2016-01-01

    There has been much interest in studying evolutionary games in structured populations, often modeled as graphs. However, most analytical results so far have only been obtained for two-player or linear games, while the study of more complex multiplayer games has been usually tackled by computer simulations. Here we investigate evolutionary multiplayer games on graphs updated with a Moran death-Birth process. For cycles, we obtain an exact analytical condition for cooperation to be favored by natural selection, given in terms of the payoffs of the game and a set of structure coefficients. For regular graphs of degree three and larger, we estimate this condition using a combination of pair approximation and diffusion approximation. For a large class of cooperation games, our approximations suggest that graph-structured populations are stronger promoters of cooperation than populations lacking spatial structure. Computer simulations validate our analytical approximations for random regular graphs and cycles, but show systematic differences for graphs with many loops such as lattices. In particular, our simulation results show that these kinds of graphs can even lead to more stringent conditions for the evolution of cooperation than well-mixed populations. Overall, we provide evidence suggesting that the complexity arising from many-player interactions and spatial structure can be captured by pair approximation in the case of random graphs, but that it need to be handled with care for graphs with high clustering. PMID:27513946

  11. Mechatronic modeling and simulation using bond graphs

    CERN Document Server

    Das, Shuvra

    2009-01-01

    Introduction to Mechatronics and System ModelingWhat Is Mechatronics?What Is a System and Why Model Systems?Mathematical Modeling Techniques Used in PracticeSoftwareBond Graphs: What Are They?Engineering SystemsPortsGeneralized VariablesBond GraphsBasic Components in SystemsA Brief Note about Bond Graph Power DirectionsSummary of Bond Direction RulesDrawing Bond Graphs for Simple Systems: Electrical and MechanicalSimplification Rules for Junction StructureDrawing Bond Graphs for Electrical SystemsDrawing Bond Graphs for Mechanical SystemsCausalityDrawing Bond Graphs for Hydraulic and Electronic Components and SystemsSome Basic Properties and Concepts for FluidsBond Graph Model of Hydraulic SystemsElectronic SystemsDeriving System Equations from Bond GraphsSystem VariablesDeriving System EquationsTackling Differential CausalityAlgebraic LoopsSolution of Model Equations and Their InterpretationZeroth Order SystemsFirst Order SystemsSecond Order SystemTransfer Functions and Frequency ResponsesNumerical Solution ...

  12. The color space of a graph

    DEFF Research Database (Denmark)

    Jensen, T.R.; Thomassen, Carsten

    2000-01-01

    If k is a prime power, and G is a graph with n vertices, then a k-coloring of G may be considered as a vector in GF(k)(n). We prove that the subspace of GF(3)(n) spanned by all 3-colorings of a planar triangle-free graph with n vertices has dimension n. In particular, any such graph has at least n...... - 1 nonequivalent 3-colorings, and the addition of any edge or any vertex of degree 3 results in a 3-colorable graph. (C) 2000 John Wiley & Sons, Inc....

  13. Graph algorithms in the titan toolkit.

    Energy Technology Data Exchange (ETDEWEB)

    McLendon, William Clarence, III; Wylie, Brian Neil

    2009-10-01

    Graph algorithms are a key component in a wide variety of intelligence analysis activities. The Graph-Based Informatics for Non-Proliferation and Counter-Terrorism project addresses the critical need of making these graph algorithms accessible to Sandia analysts in a manner that is both intuitive and effective. Specifically we describe the design and implementation of an open source toolkit for doing graph analysis, informatics, and visualization that provides Sandia with novel analysis capability for non-proliferation and counter-terrorism.

  14. Evolutionary Games of Multiplayer Cooperation on Graphs.

    Science.gov (United States)

    Peña, Jorge; Wu, Bin; Arranz, Jordi; Traulsen, Arne

    2016-08-01

    There has been much interest in studying evolutionary games in structured populations, often modeled as graphs. However, most analytical results so far have only been obtained for two-player or linear games, while the study of more complex multiplayer games has been usually tackled by computer simulations. Here we investigate evolutionary multiplayer games on graphs updated with a Moran death-Birth process. For cycles, we obtain an exact analytical condition for cooperation to be favored by natural selection, given in terms of the payoffs of the game and a set of structure coefficients. For regular graphs of degree three and larger, we estimate this condition using a combination of pair approximation and diffusion approximation. For a large class of cooperation games, our approximations suggest that graph-structured populations are stronger promoters of cooperation than populations lacking spatial structure. Computer simulations validate our analytical approximations for random regular graphs and cycles, but show systematic differences for graphs with many loops such as lattices. In particular, our simulation results show that these kinds of graphs can even lead to more stringent conditions for the evolution of cooperation than well-mixed populations. Overall, we provide evidence suggesting that the complexity arising from many-player interactions and spatial structure can be captured by pair approximation in the case of random graphs, but that it need to be handled with care for graphs with high clustering.

  15. A Reduction of the Graph Reconstruction Conjecture

    Directory of Open Access Journals (Sweden)

    Monikandan S.

    2014-08-01

    Full Text Available A graph is said to be reconstructible if it is determined up to isomor- phism from the collection of all its one-vertex deleted unlabeled subgraphs. Reconstruction Conjecture (RC asserts that all graphs on at least three vertices are reconstructible. In this paper, we prove that interval-regular graphs and some new classes of graphs are reconstructible and show that RC is true if and only if all non-geodetic and non-interval-regular blocks G with diam(G = 2 or diam(Ḡ = diam(G = 3 are reconstructible

  16. Visual Adjacency Lists for Dynamic Graphs.

    Science.gov (United States)

    Hlawatsch, Marcel; Burch, Michael; Weiskopf, Daniel

    2014-11-01

    We present a visual representation for dynamic, weighted graphs based on the concept of adjacency lists. Two orthogonal axes are used: one for all nodes of the displayed graph, the other for the corresponding links. Colors and labels are employed to identify the nodes. The usage of color allows us to scale the visualization to single pixel level for large graphs. In contrast to other techniques, we employ an asymmetric mapping that results in an aligned and compact representation of links. Our approach is independent of the specific properties of the graph to be visualized, but certain graphs and tasks benefit from the asymmetry. As we show in our results, the strength of our technique is the visualization of dynamic graphs. In particular, sparse graphs benefit from the compact representation. Furthermore, our approach uses visual encoding by size to represent weights and therefore allows easy quantification and comparison. We evaluate our approach in a quantitative user study that confirms the suitability for dynamic and weighted graphs. Finally, we demonstrate our approach for two examples of dynamic graphs.

  17. Feedback as the source of imperfection in lossy perfect lenses

    Science.gov (United States)

    Rosenblatt, Gilad; Bartal, Guy; Orenstein, Meir

    2016-02-01

    The major barrier to realizing a perfect lens with left-handed materials is perceived to be their intrinsic loss. Here we show that only specific designs of perfect lenses are limited by loss—those in which material loss is translated to internal feedback. The asymptotically uniform transmission required for perfect lensing is hindered by such feedback, which generates resonances that lead to a spatial cutoff in the lens transmission. Moreover, uniform transmission and its resonant deterioration stem from completely separate classes of modal excitations. A perfect lens made of lossy left-handed materials is therefore not forbidden in principle. Pursuing perfect lens designs that avoid internal feedback offers a path towards realization of practical perfect lenses.

  18. Analytical Treatment of Higher-Order Graphs: A Path Ordinal Method for Solving Graphs

    Directory of Open Access Journals (Sweden)

    Hala Kamal

    2017-11-01

    Full Text Available Analytical treatment of the composition of higher-order graphs representing linear relations between variables is developed. A path formalism to deal with problems in graph theory is introduced. It is shown how paths in the composed graph representing individual contributions to variables relation can be enumerated and represented by ordinals. The method allows for one to extract partial information and gives an alternative to classical graph approach.

  19. Applications of Multivalued Contractions on Graphs to Graph-Directed Iterated Function Systems

    Directory of Open Access Journals (Sweden)

    T. Dinevari

    2015-01-01

    Full Text Available We apply a fixed point result for multivalued contractions on complete metric spaces endowed with a graph to graph-directed iterated function systems. More precisely, we construct a suitable metric space endowed with a graph G and a suitable G-contraction such that its fixed points permit us to obtain more information on the attractor of a graph-directed iterated function system.

  20. Decomposing a planar graph into an independent set and a 3-degenerate graph

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2000-01-01

    We prove the conjecture made by O.V.Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and aset inducing a $3$-degenerate graph.......We prove the conjecture made by O.V.Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and aset inducing a $3$-degenerate graph....

  1. Decomposing a planar graph into an independent set and a 3-degenerate graph

    DEFF Research Database (Denmark)

    Thomassen, Carsten

    2001-01-01

    We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph. (C) 2001 Academic Press.......We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph. (C) 2001 Academic Press....

  2. Coherent perfect absorption and reflection in slow-light waveguides.

    Science.gov (United States)

    Gutman, Nadav; Sukhorukov, Andrey A; Chong, Y D; de Sterke, C Martijn

    2013-12-01

    We identify a family of unusual slow-light modes occurring in lossy multimode grating waveguides, for which either the forward or backward mode components, or both, are degenerate. In the fully degenerate case, the response can be modulated between coherent perfect absorption (zero reflection) and perfect reflection by varying the wave amplitudes in a uniform input waveguide. The perfectly absorbed wave has anomalously short absorption length, scaling as the inverse one-third power of the absorptivity.

  3. Two-particle quantum walks applied to the graph isomorphism problem

    International Nuclear Information System (INIS)

    Gamble, John King; Friesen, Mark; Zhou Dong; Joynt, Robert; Coppersmith, S. N.

    2010-01-01

    We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic graphs that noninteracting particles cannot. We obtain the following specific results. (1) We prove that quantum walks of two noninteracting particles, fermions or bosons, cannot distinguish certain pairs of nonisomorphic SRGs. (2) We demonstrate numerically that two interacting bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all nonisomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of nonisomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.

  4. Embedding graphs in Lorentzian spacetime.

    Directory of Open Access Journals (Sweden)

    James R Clough

    Full Text Available Geometric approaches to network analysis combine simply defined models with great descriptive power. In this work we provide a method for embedding directed acyclic graphs (DAG into Minkowski spacetime using Multidimensional scaling (MDS. First we generalise the classical MDS algorithm, defined only for metrics with a Riemannian signature, to manifolds of any metric signature. We then use this general method to develop an algorithm which exploits the causal structure of a DAG to assign space and time coordinates in a Minkowski spacetime to each vertex. As in the causal set approach to quantum gravity, causal connections in the discrete graph correspond to timelike separation in the continuous spacetime. The method is demonstrated by calculating embeddings for simple models of causal sets and random DAGs, as well as real citation networks. We find that the citation networks we test yield significantly more accurate embeddings that random DAGs of the same size. Finally we suggest a number of applications in citation analysis such as paper recommendation, identifying missing citations and fitting citation models to data using this geometric approach.

  5. Feature Tracking Using Reeb Graphs

    Energy Technology Data Exchange (ETDEWEB)

    Weber, Gunther H.; Bremer, Peer-Timo; Day, Marcus S.; Bell, John B.; Pascucci, Valerio

    2010-08-02

    Tracking features and exploring their temporal dynamics can aid scientists in identifying interesting time intervals in a simulation and serve as basis for performing quantitative analyses of temporal phenomena. In this paper, we develop a novel approach for tracking subsets of isosurfaces, such as burning regions in simulated flames, which are defined as areas of high fuel consumption on a temperature isosurface. Tracking such regions as they merge and split over time can provide important insights into the impact of turbulence on the combustion process. However, the convoluted nature of the temperature isosurface and its rapid movement make this analysis particularly challenging. Our approach tracks burning regions by extracting a temperature isovolume from the four-dimensional space-time temperature field. It then obtains isosurfaces for the original simulation time steps and labels individual connected 'burning' regions based on the local fuel consumption value. Based on this information, a boundary surface between burning and non-burning regions is constructed. The Reeb graph of this boundary surface is the tracking graph for burning regions.

  6. Representing vertex-transitive Vertex-transitive graphs on Groupoids

    African Journals Online (AJOL)

    Vertex-transitive graphs are one of the most favoured class of graphs in modelling scientific phenomena if symmetry is at issue. An understanding of these graphs should, therefore, be an obvious undertaking. Here, we present a characterisation of vertex-transitive graphs as left loop graphs and expose the measure of ...

  7. Graph compositions and flats of cycle matroids | Mphako-Banda ...

    African Journals Online (AJOL)

    We give an alternative method for counting the number of graph compositions of any graph G. In particular we show that counting the number of graph compositions of a graph G is equivalent to counting the number of flats of its cycle matroid. Then we give one condition for non isomorphic graphs to have the same number ...

  8. Distance-regular Cayley graphs with least eigenvalue -2

    NARCIS (Netherlands)

    van Dam, Edwin; Abdollahi, Alireza; Jazaeri, Mojtaba

    2017-01-01

    We classify the distance-regular Cayley graphs with least eigenvalue −2 and diameter at most three. Besides sporadic examples, these comprise of the lattice graphs, certain triangular graphs, and line graphs of incidence graphs of certain projective planes. In addition, we classify the possible

  9. Geometric aspects of 2-walk-regular graphs

    NARCIS (Netherlands)

    Camara Vallejo, M.; van Dam, E.R.; Koolen, J.H.; Park, J.

    2013-01-01

    A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will

  10. On cyclic orthogonal double covers of circulant graphs by special infinite graphs

    Directory of Open Access Journals (Sweden)

    R. El-Shanawany

    2017-12-01

    Full Text Available In this article, a technique to construct cyclic orthogonal double covers (CODCs of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K1,2n−10 is introduced.

  11. Helping Students Make Sense of Graphs: An Experimental Trial of SmartGraphs Software

    Science.gov (United States)

    Zucker, Andrew; Kay, Rachel; Staudt, Carolyn

    2014-01-01

    Graphs are commonly used in science, mathematics, and social sciences to convey important concepts; yet students at all ages demonstrate difficulties interpreting graphs. This paper reports on an experimental study of free, Web-based software called SmartGraphs that is specifically designed to help students overcome their misconceptions regarding…

  12. Modern problems of perfection of elite light athletic sportsmen’s technical skillfulness perfection

    Directory of Open Access Journals (Sweden)

    A.V. Kolot

    2016-04-01

    Full Text Available Purpose: perfection of elite sportsmen’s technical skillfulness in competition kinds of light athletic. Material: the data of more than 60 literature sources were systemized. Expert questioning of 36 coaches, having experience of work with elite sportsmen, was carried out; documents of training process planning were analyzed as well as sportsmen’s diaries (n=244. Results: we have presented main principles of sportsmen’s technical skillfulness perfection and elucidated characteristics of technical training methodic. We have determined main priorities of technical training building for light athletes at every stage of many years’ perfection. Dynamic of competition practice volume has been found as well as main requirements to selection of training means of technical orientation. The data of bio-mechanical criteria of sportsmen’s technical skillfulness assessment have been supplemented. Conclusions: effectiveness of sportsmen’s training methodic is determined by realization of previous stages’ technical potential in final competition results. It can be achieved by determination of means of and methods of different orientation rational correlation.

  13. Modern problems of perfection of elite light athletic sportsmen’s technical skillfulness perfection

    Directory of Open Access Journals (Sweden)

    Kolot A.V.

    2016-02-01

    Full Text Available Purpose: perfection of elite sportsmen’s technical skillfulness in competition kinds of light athletic. Material: the data of more than 60 literature sources were systemized. Expert questioning of 36 coaches, having experience of work with elite sportsmen, was carried out; documents of training process planning were analyzed as well as sportsmen’s diaries (n=244. Results: we have presented main principles of sportsmen’s technical skillfulness perfection and elucidated characteristics of technical training methodic. We have determined main priorities of technical training building for light athletes at every stage of many years’ perfection. Dynamic of competition practice volume has been found as well as main requirements to selection of training means of technical orientation. The data of bio-mechanical criteria of sportsmen’s technical skillfulness assessment have been supplemented. Conclusions: effectiveness of sportsmen’s training methodic is determined by realization of previous stages’ technical potential in final competition results. It can be achieved by determination of means of and methods of different orientation rational correlation.

  14. Enabling Graph Appliance for Genome Assembly

    Energy Technology Data Exchange (ETDEWEB)

    Singh, Rina [ORNL; Graves, Jeffrey A [ORNL; Lee, Sangkeun (Matt) [ORNL; Sukumar, Sreenivas R [ORNL; Shankar, Mallikarjun [ORNL

    2015-01-01

    In recent years, there has been a huge growth in the amount of genomic data available as reads generated from various genome sequencers. The number of reads generated can be huge, ranging from hundreds to billions of nucleotide, each varying in size. Assembling such large amounts of data is one of the challenging computational problems for both biomedical and data scientists. Most of the genome assemblers developed have used de Bruijn graph techniques. A de Bruijn graph represents a collection of read sequences by billions of vertices and edges, which require large amounts of memory and computational power to store and process. This is the major drawback to de Bruijn graph assembly. Massively parallel, multi-threaded, shared memory systems can be leveraged to overcome some of these issues. The objective of our research is to investigate the feasibility and scalability issues of de Bruijn graph assembly on Cray s Urika-GD system; Urika-GD is a high performance graph appliance with a large shared memory and massively multithreaded custom processor designed for executing SPARQL queries over large-scale RDF data sets. However, to the best of our knowledge, there is no research on representing a de Bruijn graph as an RDF graph or finding Eulerian paths in RDF graphs using SPARQL for potential genome discovery. In this paper, we address the issues involved in representing a de Bruin graphs as RDF graphs and propose an iterative querying approach for finding Eulerian paths in large RDF graphs. We evaluate the performance of our implementation on real world ebola genome datasets and illustrate how genome assembly can be accomplished with Urika-GD using iterative SPARQL queries.

  15. Practice makes two hemispheres almost perfect.

    Science.gov (United States)

    Cherbuin, Nicolas; Brinkman, Cobie

    2005-08-01

    Some tasks produce a performance advantage for conditions that require the processing of stimuli in two visual fields compared to conditions where single hemifield processing is sufficient. This advantage, however, disappears with practice. Although no definitive evidence yet exists, there are several possible mechanisms that might lead to improved performance of within- compared to across-hemisphere processing with practice. These include a shift from a more demanding, algorithmic strategy to a less demanding memory-retrieval strategy (e.g., [G. Logan, Toward an instance theory of automatisation. Psych. Rev. 95 (1988) 492-527]), as discussed by Weissman and Compton [D.H. Weissman, R.J. Compton, Practice makes a hemisphere perfect: the advantage of interhemispheric recruitment is eliminated with practice. Laterality, 8 (4) (2003) 361-375], and/or a more generalised practice effect [K. Kirsner, C. Speelman, Skill acquisition and repetition priming: one principle, many processes? J. Exp. Psychol., Learn. Mem. Cogn., 22 (1996) 563-575]. Contrary to Weissman and Compton findings, our results suggest that although single-hemisphere performance improves with practice, bi-hemispheric performance also improves substantially. Furthermore, these effects do not appear to be due to a shift in strategy but rather due to a general practice effect.

  16. The swimming of a perfect deforming helix

    Science.gov (United States)

    Koens, Lyndon; Zhang, Hang; Mourran, Ahmed; Lauga, Eric

    2017-11-01

    Many bacteria rotate helical flagellar filaments in order to swim. When at rest or rotated counter-clockwise these flagella are left handed helices but they undergo polymorphic transformations to right-handed helices when the motor is reversed. These helical deformations themselves can generate motion, with for example Rhodobacter sphaeroides using the polymorphic transformation of the flagellum to generate rotation, or Spiroplasma propagating a change of helix handedness across its body's length to generate forward motion. Recent experiments reported on an artificial helical microswimmer generating motion without a propagating change in handedness. Made of a temperature sensitive gel, these swimmers moved by changing the dimensions of the helix in a non-reciprocal way. Inspired by these results and helix's ubiquitous presence in the bacterial world, we investigate how a deforming helix moves within a viscous fluid. Maintaining a single handedness along its entire length, we discuss how a perfect deforming helix can create a non-reciprocal swimming stroke, identify its principle directions of motion, and calculate the swimming kinematics asymptotically.

  17. Perfect crystal interferometer and its applications

    Energy Technology Data Exchange (ETDEWEB)

    Hasegawa, Yuji [Atominstitut der Oesterreichischen Universitaeten, Vienna (Austria)

    1996-08-01

    The interferometry with angstrom scale wavelength has developed steadily, and various types of interferometers have been investigated. Among them, LLL interferometers are widely used. The first neutron interferometry was achieved in 1962 by Maier-Leibnitz et al. A new type of neutron interferometers was constructed with a perfect crystal, and experimentally performed in 1974 by Rauch et al. The precise measurements with LLL neutron interferometers were performed on scattering length, gravitational effect, coherence, Fizeau effects, spin superposition, complementarity, and post-selection effects. Since the early stage of quantum physics, the double-slit experiment has served as the example of the epistemologically strange features of quantum phenomena, and its course of study is described. The time-delayed interferometry with nuclear resonant scattering of synchrotron radiation and phase transfer in time-delayed interferometry with nuclear resonant scattering were experimented, and are briefly reported. A geometric phase factor was derived for a split beam experiment as an example of cyclic evolution. The geometric phase was observed with a two-loop neutron interferometer. All the experimental results showed complete agreement with the theoretical treatment. (K.I.)

  18. Band connectivity for topological quantum chemistry: Band structures as a graph theory problem

    Science.gov (United States)

    Bradlyn, Barry; Elcoro, L.; Vergniory, M. G.; Cano, Jennifer; Wang, Zhijun; Felser, C.; Aroyo, M. I.; Bernevig, B. Andrei

    2018-01-01

    The conventional theory of solids is well suited to describing band structures locally near isolated points in momentum space, but struggles to capture the full, global picture necessary for understanding topological phenomena. In part of a recent paper [B. Bradlyn et al., Nature (London) 547, 298 (2017), 10.1038/nature23268], we have introduced the way to overcome this difficulty by formulating the problem of sewing together many disconnected local k .p band structures across the Brillouin zone in terms of graph theory. In this paper, we give the details of our full theoretical construction. We show that crystal symmetries strongly constrain the allowed connectivities of energy bands, and we employ graph theoretic techniques such as graph connectivity to enumerate all the solutions to these constraints. The tools of graph theory allow us to identify disconnected groups of bands in these solutions, and so identify topologically distinct insulating phases.

  19. A Structural-Lexical Measure of Semantic Similarity for Geo-Knowledge Graphs

    Directory of Open Access Journals (Sweden)

    Andrea Ballatore

    2015-04-01

    Full Text Available Graphs have become ubiquitous structures to encode geographic knowledge online. The Semantic Web’s linked open data, folksonomies, wiki websites and open gazetteers can be seen as geo-knowledge graphs, that is labeled graphs whose vertices represent geographic concepts and whose edges encode the relations between concepts. To compute the semantic similarity of concepts in such structures, this article defines the network-lexical similarity measure (NLS. This measure estimates similarity by combining two complementary sources of information: the network similarity of vertices and the semantic similarity of the lexical definitions. NLS is evaluated on the OpenStreetMap Semantic Network, a crowdsourced geo-knowledge graph that describes geographic concepts. The hybrid approach outperforms both network and lexical measures, obtaining very strong correlation with the similarity judgments of human subjects.

  20. Stress regularity in quasi-static perfect plasticity with a pressure dependent yield criterion

    Science.gov (United States)

    Babadjian, Jean-François; Mora, Maria Giovanna

    2018-04-01

    This work is devoted to establishing a regularity result for the stress tensor in quasi-static planar isotropic linearly elastic - perfectly plastic materials obeying a Drucker-Prager or Mohr-Coulomb yield criterion. Under suitable assumptions on the data, it is proved that the stress tensor has a spatial gradient that is locally squared integrable. As a corollary, the usual measure theoretical flow rule is expressed in a strong form using the quasi-continuous representative of the stress.

  1. Graphs, Ideal Flow, and the Transportation Network

    OpenAIRE

    Teknomo, Kardi

    2016-01-01

    This lecture discusses the mathematical relationship between network structure and network utilization of transportation network. Network structure means the graph itself. Network utilization represent the aggregation of trajectories of agents in using the network graph. I show the similarity and relationship between the structural pattern of the network and network utilization.

  2. Radio Channel Modelling Using Stochastic Propagation Graphs

    DEFF Research Database (Denmark)

    Pedersen, Troels; Fleury, Bernard Henri

    2007-01-01

    In this contribution the radio channel model proposed in [1] is extended to include multiple transmitters and receivers. The propagation environment is modelled using random graphs where vertices of a graph represent scatterers and edges model the wave propagation between scatterers. Furthermore...

  3. The Minimum Distance of Graph Codes

    DEFF Research Database (Denmark)

    Høholdt, Tom; Justesen, Jørn

    2011-01-01

    We study codes constructed from graphs where the code symbols are associated with the edges and the symbols connected to a given vertex are restricted to be codewords in a component code. In particular we treat such codes from bipartite expander graphs coming from Euclidean planes and other...

  4. Geometric classification of simple graph algebras

    DEFF Research Database (Denmark)

    Sørensen, Adam Peder Wie

    2013-01-01

    Inspired by Franks’ classification of irreducible shifts of finite type, we provide a short list of allowed moves on graphs that preserve the stable isomorphism class of the associated C ∗ -algebras. We show that if two graphs have stably isomorphic and simple unital algebras then we can use...

  5. From concatenated codes to graph codes

    DEFF Research Database (Denmark)

    Justesen, Jørn; Høholdt, Tom

    2004-01-01

    We consider codes based on simple bipartite expander graphs. These codes may be seen as the first step leading from product type concatenated codes to more complex graph codes. We emphasize constructions of specific codes of realistic lengths, and study the details of decoding by message passing...

  6. Three Syntactic Theories for Combinatory Graph Reduction

    DEFF Research Database (Denmark)

    Danvy, Olivier; Zerny, Ian

    2013-01-01

    here therefore properly account for combinatory graph reduction As We Know It. These three syntactic theories scale to handling the Y combinator. This article therefore illustrates the scientic consensus of theoreticians and implementors about graph reduction: it is the same combinatory elephant....

  7. Edge Cover Domination in Mangoldt Graph

    African Journals Online (AJOL)

    Bheema

    Domination theory of graphs has many applications in. Engineering and Communication Networks. For these applications, the arithmetic graphs associated with certain number theoretic arithmetic functions like the Euler totient function Φ(n), the divison function d(n), the quadratic residue function and the Mangoldt function ...

  8. Attitudes towards Graphing Calculators in Developmental Mathematics

    Science.gov (United States)

    Rajan, Shaun Thomas

    2013-01-01

    The purpose of this exploratory study was to examine instructor and student attitudes towards the use of the graphing calculator in the developmental mathematics classroom. A focus of the study was to see if instructors or students believed there were changes in the conceptual understanding of mathematics as a result of graphing calculator…

  9. A Graph Library Extension of SVG

    DEFF Research Database (Denmark)

    Nørmark, Kurt

    2007-01-01

    be aggregated as a single node, and an entire graph can be embedded in a single node. In addition, a number of different graph animations are described. The starting point of the SVG extension is a library that provides an exact of mirror of SVG 1.1 in the functional programming language Scheme. Each element...

  10. Eigenvalues and expansion of bipartite graphs

    DEFF Research Database (Denmark)

    Høholdt, Tom; Janwa, Heeralal

    2012-01-01

    We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes that are optimal with respect to the bouns. We prove that BIBD-graphs are characterized by ...

  11. Student Reasoning about Graphs in Different Contexts

    Science.gov (United States)

    Ivanjek, Lana; Susac, Ana; Planinic, Maja; Andrasevic, Aneta; Milin-Sipus, Zeljka

    2016-01-01

    This study investigates university students' graph interpretation strategies and difficulties in mathematics, physics (kinematics), and contexts other than physics. Eight sets of parallel (isomorphic) mathematics, physics, and other context questions about graphs, which were developed by us, were administered to 385 first-year students at the…

  12. Acyclicity in edge-colored graphs

    DEFF Research Database (Denmark)

    Gutin, Gregory; Jones, Mark; Sheng, Bin

    2017-01-01

    A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type i......+1, i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored...... graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex...

  13. Sobolev spaces on graphs | Ostrovskii | Quaestiones Mathematicae

    African Journals Online (AJOL)

    The present paper is devoted to discrete analogues of Sobolev spaces of smooth functions. The discrete analogues that we consider are spaces of functions on vertex sets of graphs. Such spaces have applications in Graph Theory, Metric Geometry and Convex Geometry. We present known and prove some new results on ...

  14. Pattern Perception and the Comprehension of Graphs.

    Science.gov (United States)

    Pinker, Steven

    Three experiments tested the hypothesis that graphs convey information effectively because they can display global trends as geometric patterns that visual systems encode easily. A novel type of graph was invented in which angles/lengths of line segments joined end-to-end represented variables of rainfall and temperature of a set of months. It was…

  15. Knowledge graph analysis of particles in Japanese

    NARCIS (Netherlands)

    Hoede, C.

    2005-01-01

    The theory of knowledge graphs is a structuralistic theory of language. Its ontology consists of eight types of binary relationships and four types of so-called frames. The relationships connect so-called tokens, that represent semantic units. In this way a graph structure arises. Japanese particles

  16. Graph coarsening and clustering on the GPU

    NARCIS (Netherlands)

    Fagginger Auer, B.O.; Bisseling, R.H.

    2013-01-01

    Agglomerative clustering is an effective greedy way to quickly generate graph clusterings of high modularity in a small amount of time. In an effort to use the power offered by multi-core CPU and GPU hardware to solve the clustering problem, we introduce a fine-grained sharedmemory parallel graph

  17. Chain graph models and their causal interpretations

    DEFF Research Database (Denmark)

    Lauritzen, Steffen Lilholt; Richardson, Thomas S.

    2002-01-01

    , interpretations of chain graphs that are often invoked, implicitly or explicitly. These interpretations also lead to flawed methods for applying background knowledge to model selection. We present a valid interpretation by showing how the distribution corresponding to a chain graph may be generated from...... traditionally been used to model feed-back in econometrics....

  18. Dynamic planar embeddings of dynamic graphs

    DEFF Research Database (Denmark)

    Holm, Jacob; Rotenberg, Eva

    2017-01-01

    , exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common...

  19. Dynamic planar embeddings of dynamic graphs

    DEFF Research Database (Denmark)

    Holm, Jacob; Rotenberg, Eva

    2015-01-01

    that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour....

  20. An analysis of facebook's graph search

    CSIR Research Space (South Africa)

    Khan, ZC

    2014-11-01

    Full Text Available digital media. With the large number of users active on Facebook, an upgrade to Facebook’s searching capability was made through the launch of graph search. Graph search is a powerful search feature which allows users to search Facebook using queries...

  1. Connected domination stable graphs upon edge addition ...

    African Journals Online (AJOL)

    A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number. Keywords: Connected domination, connected domination stable, edge addition ...

  2. A Ring Construction Using Finite Directed Graphs

    Science.gov (United States)

    Bardzell, Michael

    2012-01-01

    In this paper we discuss an interesting class of noncommutative rings which can be constructed using finite directed graphs. This construction also creates a vector space. These structures provide undergraduate students connections between ring theory and graph theory and, among other things, allow them to see a ring unity element that looks quite…

  3. Toughness and Triangle-Free Graphs

    NARCIS (Netherlands)

    Bauer, D.; van den Heuvel, J.; Schmeichel, E.

    1995-01-01

    In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a

  4. Declarative Process Mining for DCR Graphs

    DEFF Research Database (Denmark)

    Debois, Søren; Hildebrandt, Thomas T.; Laursen, Paw Høvsgaard

    2017-01-01

    We investigate process mining for the declarative Dynamic Condition Response (DCR) graphs process modelling language. We contribute (a) a process mining algorithm for DCR graphs, (b) a proposal for a set of metrics quantifying output model quality, and (c) a preliminary example-based comparison...

  5. Graph Bundling by Kernel Density Estimation

    NARCIS (Netherlands)

    Hurter, C.; Ersoy, O.; Telea, A.

    We present a fast and simple method to compute bundled layouts of general graphs. For this, we first transform a given graph drawing into a density map using kernel density estimation. Next, we apply an image sharpening technique which progressively merges local height maxima by moving the convolved

  6. The direct algorithm for solving of the graph isomorphism problem

    OpenAIRE

    Faizullin, Rashit T.; Prolubnikov, Alexander V.

    2005-01-01

    We propose an algorithm for solving of the graph isomorphism problem. Also, we introduce the new class of graphs for which the graph isomorphism problem can be solved polynomially using the algorithm.

  7. Proof-graphs for Minimal Implicational Logic

    Directory of Open Access Journals (Sweden)

    Marcela Quispe-Cruz

    2014-03-01

    Full Text Available It is well-known that the size of propositional classical proofs can be huge. Proof theoretical studies discovered exponential gaps between normal or cut free proofs and their respective non-normal proofs. The aim of this work is to study how to reduce the weight of propositional deductions. We present the formalism of proof-graphs for purely implicational logic, which are graphs of a specific shape that are intended to capture the logical structure of a deduction. The advantage of this formalism is that formulas can be shared in the reduced proof. In the present paper we give a precise definition of proof-graphs for the minimal implicational logic, together with a normalization procedure for these proof-graphs. In contrast to standard tree-like formalisms, our normalization does not increase the number of nodes, when applied to the corresponding minimal proof-graph representations.

  8. A model of language inflection graphs

    Science.gov (United States)

    Fukś, Henryk; Farzad, Babak; Cao, Yi

    2014-01-01

    Inflection graphs are highly complex networks representing relationships between inflectional forms of words in human languages. For so-called synthetic languages, such as Latin or Polish, they have particularly interesting structure due to the abundance of inflectional forms. We construct the simplest form of inflection graphs, namely a bipartite graph in which one group of vertices corresponds to dictionary headwords and the other group to inflected forms encountered in a given text. We, then, study projection of this graph on the set of headwords. The projection decomposes into a large number of connected components, to be called word groups. Distribution of sizes of word group exhibits some remarkable properties, resembling cluster distribution in a lattice percolation near the critical point. We propose a simple model which produces graphs of this type, reproducing the desired component distribution and other topological features.

  9. Algorithms for Graph Rigidity and Scene Analysis

    DEFF Research Database (Denmark)

    Berg, Alex Rune; Jordán, Tibor

    2003-01-01

    We investigate algorithmic questions and structural problems concerning graph families defined by `edge-counts'. Motivated by recent developments in the unique realization problem of graphs, we give an efficient algorithm to compute the rigid, redundantly rigid, M-connected, and globally rigid...... components of a graph. Our algorithm is based on (and also extends and simplifies) the idea of Hendrickson and Jacobs, as it uses orientations as the main algorithmic tool. We also consider families of bipartite graphs which occur in parallel drawings and scene analysis. We verify a conjecture of Whiteley...... by showing that 2d-connected bipartite graphs are d-tight. We give a new algorithm for finding a maximal d-sharp subgraph. We also answer a question of Imai and show that finding a maximum size d-sharp subgraph is NP-hard....

  10. On The Roman Domination Stable Graphs

    Directory of Open Access Journals (Sweden)

    Hajian Majid

    2017-11-01

    Full Text Available A Roman dominating function (or just RDF on a graph G = (V,E is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u = 0 is adjacent to at least one vertex v for which f(v = 2. The weight of an RDF f is the value f(V (G = Pu2V (G f(u. The Roman domination number of a graph G, denoted by R(G, is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under removal of any vertex. In this paper we present upper bounds for the Roman domination number in the class of Roman domination stable graphs, improving bounds posed in [V. Samodivkin, Roman domination in graphs: the class RUV R, Discrete Math. Algorithms Appl. 8 (2016 1650049].

  11. Disease management research using event graphs.

    Science.gov (United States)

    Allore, H G; Schruben, L W

    2000-08-01

    Event Graphs, conditional representations of stochastic relationships between discrete events, simulate disease dynamics. In this paper, we demonstrate how Event Graphs, at an appropriate abstraction level, also extend and organize scientific knowledge about diseases. They can identify promising treatment strategies and directions for further research and provide enough detail for testing combinations of new medicines and interventions. Event Graphs can be enriched to incorporate and validate data and test new theories to reflect an expanding dynamic scientific knowledge base and establish performance criteria for the economic viability of new treatments. To illustrate, an Event Graph is developed for mastitis, a costly dairy cattle disease, for which extensive scientific literature exists. With only a modest amount of imagination, the methodology presented here can be seen to apply modeling to any disease, human, plant, or animal. The Event Graph simulation presented here is currently being used in research and in a new veterinary epidemiology course. Copyright 2000 Academic Press.

  12. Pixels to Graphs by Associative Embedding

    KAUST Repository

    Newell, Alejandro

    2017-06-22

    Graphs are a useful abstraction of image content. Not only can graphs represent details about individual objects in a scene but they can capture the interactions between pairs of objects. We present a method for training a convolutional neural network such that it takes in an input image and produces a full graph. This is done end-to-end in a single stage with the use of associative embeddings. The network learns to simultaneously identify all of the elements that make up a graph and piece them together. We benchmark on the Visual Genome dataset, and report a Recall@50 of 9.7% compared to the prior state-of-the-art at 3.4%, a nearly threefold improvement on the challenging task of scene graph generation.

  13. Pristine transfinite graphs and permissive electrical networks

    CERN Document Server

    Zemanian, Armen H

    2001-01-01

    A transfinite graph or electrical network of the first rank is obtained conceptually by connecting conventionally infinite graphs and networks together at their infinite extremities. This process can be repeated to obtain a hierarchy of transfiniteness whose ranks increase through the countable ordinals. This idea, which is of recent origin, has enriched the theories of graphs and networks with radically new constructs and research problems. The book provides a more accessible introduction to the subject that, though sacrificing some generality, captures the essential ideas of transfiniteness for graphs and networks. Thus, for example, some results concerning discrete potentials and random walks on transfinite networks can now be presented more concisely. Conversely, the simplifications enable the development of many new results that were previously unavailable. Topics and features: *A simplified exposition provides an introduction to transfiniteness for graphs and networks.*Various results for conventional g...

  14. Graph Mining Meets the Semantic Web

    Energy Technology Data Exchange (ETDEWEB)

    Lee, Sangkeun (Matt) [ORNL; Sukumar, Sreenivas R [ORNL; Lim, Seung-Hwan [ORNL

    2015-01-01

    The Resource Description Framework (RDF) and SPARQL Protocol and RDF Query Language (SPARQL) were introduced about a decade ago to enable flexible schema-free data interchange on the Semantic Web. Today, data scientists use the framework as a scalable graph representation for integrating, querying, exploring and analyzing data sets hosted at different sources. With increasing adoption, the need for graph mining capabilities for the Semantic Web has emerged. We address that need through implementation of three popular iterative Graph Mining algorithms (Triangle count, Connected component analysis, and PageRank). We implement these algorithms as SPARQL queries, wrapped within Python scripts. We evaluate the performance of our implementation on 6 real world data sets and show graph mining algorithms (that have a linear-algebra formulation) can indeed be unleashed on data represented as RDF graphs using the SPARQL query interface.

  15. OPEX: Optimized Eccentricity Computation in Graphs

    Energy Technology Data Exchange (ETDEWEB)

    Henderson, Keith [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)

    2011-11-14

    Real-world graphs have many properties of interest, but often these properties are expensive to compute. We focus on eccentricity, radius and diameter in this work. These properties are useful measures of the global connectivity patterns in a graph. Unfortunately, computing eccentricity for all nodes is O(n2) for a graph with n nodes. We present OPEX, a novel combination of optimizations which improves computation time of these properties by orders of magnitude in real-world experiments on graphs of many different sizes. We run OPEX on graphs with up to millions of links. OPEX gives either exact results or bounded approximations, unlike its competitors which give probabilistic approximations or sacrifice node-level information (eccentricity) to compute graphlevel information (diameter).

  16. Relations between the set-complexity and the structure of graphs and their sub-graphs.

    Science.gov (United States)

    Ignac, Tomasz M; Sakhanenko, Nikita A; Galas, David J

    2012-09-21

    : We describe some new conceptual tools for the rigorous, mathematical description of the "set-complexity" of graphs. This set-complexity has been shown previously to be a useful measure for analyzing some biological networks, and in discussing biological information in a quantitative fashion. The advances described here allow us to define some significant relationships between the set-complexity measure and the structure of graphs, and of their component sub-graphs. We show here that modular graph structures tend to maximize the set-complexity of graphs. We point out the relationship between modularity and redundancy, and discuss the significance of set-complexity in this regard. We specifically discuss the relationship between complexity and entropy in the case of complete-bipartite graphs, and present a new method for constructing highly complex, binary graphs. These results can be extended to the case of ternary graphs, and to other multi-edge graphs, which are fundamentally more relevant to biological structures and systems. Finally, our results lead us to an approach for extracting high complexity modular graphs from large, noisy graphs with low information content. We illustrate this approach with two examples.

  17. Toughness Condition for a Graph to Be a Fractional (g,f,n-Critical Deleted Graph

    Directory of Open Access Journals (Sweden)

    Wei Gao

    2014-01-01

    Full Text Available A graph G is called a fractional (g,f-deleted graph if G-{e} admits a fractional (g,f-factor for any e∈E(G. A graph G is called a fractional (g,f,n-critical deleted graph if, after deleting any n vertices from G, the resulting graph is still a fractional (g,f-deleted graph. The toughness, as the parameter for measuring the vulnerability of communication networks, has received significant attention in computer science. In this paper, we present the relationship between toughness and fractional (g,f,n-critical deleted graphs. It is determined that G is fractional (g,f,n-critical deleted if t(G≥((b2-1+bn/a.

  18. Inferring ontology graph structures using OWL reasoning.

    Science.gov (United States)

    Rodríguez-García, Miguel Ángel; Hoehndorf, Robert

    2018-01-05

    Ontologies are representations of a conceptualization of a domain. Traditionally, ontologies in biology were represented as directed acyclic graphs (DAG) which represent the backbone taxonomy and additional relations between classes. These graphs are widely exploited for data analysis in the form of ontology enrichment or computation of semantic similarity. More recently, ontologies are developed in a formal language such as the Web Ontology Language (OWL) and consist of a set of axioms through which classes are defined or constrained. While the taxonomy of an ontology can be inferred directly from the axioms of an ontology as one of the standard OWL reasoning tasks, creating general graph structures from OWL ontologies that exploit the ontologies' semantic content remains a challenge. We developed a method to transform ontologies into graphs using an automated reasoner while taking into account all relations between classes. Searching for (existential) patterns in the deductive closure of ontologies, we can identify relations between classes that are implied but not asserted and generate graph structures that encode for a large part of the ontologies' semantic content. We demonstrate the advantages of our method by applying it to inference of protein-protein interactions through semantic similarity over the Gene Ontology and demonstrate that performance is increased when graph structures are inferred using deductive inference according to our method. Our software and experiment results are available at http://github.com/bio-ontology-research-group/Onto2Graph . Onto2Graph is a method to generate graph structures from OWL ontologies using automated reasoning. The resulting graphs can be used for improved ontology visualization and ontology-based data analysis.

  19. Inferring ontology graph structures using OWL reasoning

    KAUST Repository

    Rodriguez-Garcia, Miguel Angel

    2018-01-05

    Ontologies are representations of a conceptualization of a domain. Traditionally, ontologies in biology were represented as directed acyclic graphs (DAG) which represent the backbone taxonomy and additional relations between classes. These graphs are widely exploited for data analysis in the form of ontology enrichment or computation of semantic similarity. More recently, ontologies are developed in a formal language such as the Web Ontology Language (OWL) and consist of a set of axioms through which classes are defined or constrained. While the taxonomy of an ontology can be inferred directly from the axioms of an ontology as one of the standard OWL reasoning tasks, creating general graph structures from OWL ontologies that exploit the ontologies\\' semantic content remains a challenge.We developed a method to transform ontologies into graphs using an automated reasoner while taking into account all relations between classes. Searching for (existential) patterns in the deductive closure of ontologies, we can identify relations between classes that are implied but not asserted and generate graph structures that encode for a large part of the ontologies\\' semantic content. We demonstrate the advantages of our method by applying it to inference of protein-protein interactions through semantic similarity over the Gene Ontology and demonstrate that performance is increased when graph structures are inferred using deductive inference according to our method. Our software and experiment results are available at http://github.com/bio-ontology-research-group/Onto2Graph .Onto2Graph is a method to generate graph structures from OWL ontologies using automated reasoning. The resulting graphs can be used for improved ontology visualization and ontology-based data analysis.

  20. The Ideology of the Perfect Dictionary: How Efficient Can a ...

    African Journals Online (AJOL)

    There is no perfect student. Language learners, for whom dictionaries are of great importance, seek user-friendly material which will improve both their fluency in and understanding of the target language, and embed acquired lexis in their long-term memory. Lexicographers, in their search for perfection and in compliance ...

  1. Tie-breaking in games of perfect information

    DEFF Research Database (Denmark)

    Tranæs, Torben

    1998-01-01

    The paper suggests that ties in an extensive form game have strategic implications if they represent credible threats or promises. We consider a subset of subgame-perfect Nash equilibria obtained by breaking ties according to their strategic implications, and show that the subset is nonempty for ...... for finite extensive form games of perfect information....

  2. Bianchi type-I massive string magnetized barotropic perfect fluid ...

    Indian Academy of Sciences (India)

    by either a perfect fluid or a cosmic string in bimetric theory of gravitation. Bali and Prad- han [41] have investigated Bianchi type-III string cosmological model with time-dependent bulk viscosity. In view of the importance of Maxwell's electromagnetic field interactions with a perfect fluid or a cosmic string and there is a lot of ...

  3. Development of a perfect prognosis probabilistic model for ...

    Indian Academy of Sciences (India)

    A prediction model based on the perfect prognosis method was developed to predict the probability of lightning and probable time of its occurrence over the south-east Indian region. In the perfect prognosis method, statistical relationships are established using past observed data. For real time applications, the predictors ...

  4. The Ideology of the Perfect Dictionary: How Efficient Can a ...

    African Journals Online (AJOL)

    rbr

    curiosities, archaisms and other vestiges from the past conserved in dictionaries. Is the concept of a perfect dictionary a reality or an ideal? There is no perfect student. Language learners, for whom dictionaries are of great importance, seek user-friendly material which will improve both their fluency in and understanding of ...

  5. Lattice fluid dynamics from perfect discretizations of continuum flows

    International Nuclear Information System (INIS)

    Katz, E.; Wiese, U.

    1998-01-01

    We use renormalization group methods to derive equations of motion for large scale variables in fluid dynamics. The large scale variables are averages of the underlying continuum variables over cubic volumes and naturally exist on a lattice. The resulting lattice dynamics represents a perfect discretization of continuum physics, i.e., grid artifacts are completely eliminated. Perfect equations of motion are derived for static, slow flows of incompressible, viscous fluids. For Hagen-Poiseuille flow in a channel with a square cross section the equations reduce to a perfect discretization of the Poisson equation for the velocity field with Dirichlet boundary conditions. The perfect large scale Poisson equation is used in a numerical simulation and is shown to represent the continuum flow exactly. For nonsquare cross sections one can use a numerical iterative procedure to derive flow equations that are approximately perfect. copyright 1998 The American Physical Society

  6. Spanners for geometric intersection graphs with applications

    Directory of Open Access Journals (Sweden)

    Martin Fürer

    2012-05-01

    Full Text Available A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real numbert>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of verticesu,v in G, there exists a path in G' of length at most t times the distance between u and v inG. In this paper, we consider the problem of efficiently constructing sparse spanners of ball graphs which supports fast shortest path distance queries.We present the first algorithm for constructing spanners of ball graphs. For a ball graph in Rk, we construct a (1+ε-spanner for any ε>0 with O(nε-k+1 edges in O(n2ℓ+δε-k logℓ S time, using an efficient partitioning of space into hypercubes and solving intersection problems. Here ℓ=1-1/(⌊k/2⌋+2, δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case when the balls all have unit size, we show that the complexity of constructing a (1+ε-spanner is almost equal to the complexity of constructing a Euclidean minimum spanning tree. The algorithm extends naturally to other disk-likeobjects, also in higher dimensions.The algorithm uses an efficient subdivision of space to construct a sparse graph having many of the same distance properties as the input ball graph. Additionally, the constructed spanners have a small vertex separator decomposition (hereditary. In dimension k=2, the disk graph spanner has an O(n1/2ε-3/2+ε-3log S separator. The presence of a small separator is then exploited to obtain very efficient data structures for approximate distance queries. The results on geometric graph separators might be of independent interest. For example, since complete Euclidean graphs are just a special case of (unit ball graphs, our results also provide a new approach for constructing spanners with small separators in these graphs.

  7. Exact EGB models for spherical static perfect fluids

    Energy Technology Data Exchange (ETDEWEB)

    Hansraj, Sudan; Chilambwe, Brian; Maharaj, Sunil D. [University of KwaZulu-Natal, Astrophysics and Cosmology Research Unit, School of Mathematics, Statistics and Computer Science, Private Bag 54001, Durban (South Africa)

    2015-06-15

    We obtain a new exact solution to the field equations for a 5-dimensional spherically symmetric static distribution in the Einstein-Gauss-Bonnet modified theory of gravity. By using a transformation, the study is reduced to the analysis of a single second order nonlinear differential equation. In general the condition of pressure isotropy produces a first order differential equation which is an Abel equation of the second kind. An exact solution is found. The solution is examined for physical admissibility. In particular a set of constants is found which ensures that a pressure-free hypersurface exists which defines the boundary of the distribution. Additionally the isotropic pressure and the energy density are shown to be positive within the radius of the sphere. The adiabatic sound-speed criterion is also satisfied within the fluid ensuring a subluminal sound speed. Furthermore, the weak, strong and dominant conditions hold throughout the distribution. On setting the Gauss-Bonnet coupling to zero, an exact solution for 5-dimensional perfect fluids in the standard Einstein theory is obtained. Plots of the dynamical quantities for the Gauss-Bonnet and the Einstein case reveal that the pressure is unaffected, while the energy density increases under the influence of the Gauss-Bonnet term. (orig.)

  8. Discriminative graph embedding for label propagation.

    Science.gov (United States)

    Nguyen, Canh Hao; Mamitsuka, Hiroshi

    2011-09-01

    In many applications, the available information is encoded in graph structures. This is a common problem in biological networks, social networks, web communities and document citations. We investigate the problem of classifying nodes' labels on a similarity graph given only a graph structure on the nodes. Conventional machine learning methods usually require data to reside in some Euclidean spaces or to have a kernel representation. Applying these methods to nodes on graphs would require embedding the graphs into these spaces. By embedding and then learning the nodes on graphs, most methods are either flexible with different learning objectives or efficient enough for large scale applications. We propose a method to embed a graph into a feature space for a discriminative purpose. Our idea is to include label information into the embedding process, making the space representation tailored to the task. We design embedding objective functions that the following learning formulations become spectral transforms. We then reformulate these spectral transforms into multiple kernel learning problems. Our method, while being tailored to the discriminative tasks, is efficient and can scale to massive data sets. We show the need of discriminative embedding on some simulations. Applying to biological network problems, our method is shown to outperform baselines.

  9. Graph-theoretical concepts and physicochemical data

    Directory of Open Access Journals (Sweden)

    Lionello Pogliani

    2003-02-01

    Full Text Available Graph theoretical concepts have been used to model the molecular polarizabilities of fifty-four organic derivatives, and the induced dipole moment of a set of fifty-seven organic compounds divided into three subsets. The starting point of these modeling strategies is the hydrogen-suppressed chemical graph and pseudograph of a molecule, which works very well for second row atoms. From these types of graphs a set of graph-theoretical basis indices, the molecular connectivity indices, can be derived and used to model properties and activities of molecules. With the aid of the molecular connectivity basis indices it is then possible to build higher-order descriptors. The problem of 'graph' encoding the contribution of the inner-core electrons of heteroatoms can here be solved with the aid of odd complete graphs, Kp-(p-odd. The use of these graph tools allow to draw an optimal modeling of the molecular polarizabilities and a satisfactory modeling of the induced dipole moment of a wide set of organic derivatives.

  10. Pathfinder: Visual Analysis of Paths in Graphs

    Science.gov (United States)

    Partl, C.; Gratzl, S.; Streit, M.; Wassermann, A. M.; Pfister, H.; Schmalstieg, D.; Lex, A.

    2016-01-01

    The analysis of paths in graphs is highly relevant in many domains. Typically, path-related tasks are performed in node-link layouts. Unfortunately, graph layouts often do not scale to the size of many real world networks. Also, many networks are multivariate, i.e., contain rich attribute sets associated with the nodes and edges. These attributes are often critical in judging paths, but directly visualizing attributes in a graph layout exacerbates the scalability problem. In this paper, we present visual analysis solutions dedicated to path-related tasks in large and highly multivariate graphs. We show that by focusing on paths, we can address the scalability problem of multivariate graph visualization, equipping analysts with a powerful tool to explore large graphs. We introduce Pathfinder (Figure 1), a technique that provides visual methods to query paths, while considering various constraints. The resulting set of paths is visualized in both a ranked list and as a node-link diagram. For the paths in the list, we display rich attribute data associated with nodes and edges, and the node-link diagram provides topological context. The paths can be ranked based on topological properties, such as path length or average node degree, and scores derived from attribute data. Pathfinder is designed to scale to graphs with tens of thousands of nodes and edges by employing strategies such as incremental query results. We demonstrate Pathfinder's fitness for use in scenarios with data from a coauthor network and biological pathways. PMID:27942090

  11. Pathfinder: Visual Analysis of Paths in Graphs.

    Science.gov (United States)

    Partl, C; Gratzl, S; Streit, M; Wassermann, A M; Pfister, H; Schmalstieg, D; Lex, A

    2016-06-01

    The analysis of paths in graphs is highly relevant in many domains. Typically, path-related tasks are performed in node-link layouts. Unfortunately, graph layouts often do not scale to the size of many real world networks. Also, many networks are multivariate, i.e., contain rich attribute sets associated with the nodes and edges. These attributes are often critical in judging paths, but directly visualizing attributes in a graph layout exacerbates the scalability problem. In this paper, we present visual analysis solutions dedicated to path-related tasks in large and highly multivariate graphs. We show that by focusing on paths, we can address the scalability problem of multivariate graph visualization, equipping analysts with a powerful tool to explore large graphs. We introduce Pathfinder (Figure 1), a technique that provides visual methods to query paths, while considering various constraints. The resulting set of paths is visualized in both a ranked list and as a node-link diagram. For the paths in the list, we display rich attribute data associated with nodes and edges, and the node-link diagram provides topological context. The paths can be ranked based on topological properties, such as path length or average node degree, and scores derived from attribute data. Pathfinder is designed to scale to graphs with tens of thousands of nodes and edges by employing strategies such as incremental query results. We demonstrate Pathfinder's fitness for use in scenarios with data from a coauthor network and biological pathways.

  12. A first course in graph theory

    CERN Document Server

    Chartrand, Gary

    2012-01-01

    This comprehensive text offers undergraduates a remarkably student-friendly introduction to graph theory. Written by two of the field's most prominent experts, it takes an engaging approach that emphasizes graph theory's history. Unique examples and lucid proofs provide a sound yet accessible treatment that stimulates interest in an evolving subject and its many applications.Optional sections designated as ""excursion"" and ""exploration"" present interesting sidelights of graph theory and touch upon topics that allow students the opportunity to experiment and use their imaginations. Three app

  13. NOUS: A Knowledge Graph Management System

    Energy Technology Data Exchange (ETDEWEB)

    2017-06-26

    Knowledge graphs represent information as entities and relationships between them. For tasks such as natural language question answering or automated analysis of text, a knowledge graph provides valuable context to establish the specific type of entities being discussed. It allow us to derive better context about newly arriving information and leads to intelligent reasoning capabilities. We address two primary needs: A) Automated construction of knowledge graphs is a technically challenging, expensive process; and B) The ability to synthesize new information by monitoring newly emerging knowledge is a transformational capability that does not exist in state of the art systems.

  14. The total irregularity of a graph

    DEFF Research Database (Denmark)

    Abdo, H.; Brandt, S.; Dimitrov, D.

    2014-01-01

    In this note a new measure of irregularity of a graph G is introduced. It is named the total irregularity of a graph and is defined as irr(t)(G) - 1/2 Sigma(u, v is an element of V(G)) vertical bar d(G)(u) - d(G)(v)vertical bar, where d(G)(u) denotes the degree of a vertex u is an element of V......(G). All graphs with maximal total irregularity are determined. It is also shown that among all trees of the same order the star has the maximal total irregularity....

  15. Crossed products for interactions and graph algebras

    DEFF Research Database (Denmark)

    Kwasniewski, Bartosz

    2014-01-01

    . These results cover the case of crossed products by endomorphisms with hereditary ranges and complemented kernels. As model examples of interactions not coming from endomorphisms we introduce and study in detail interactions arising from finite graphs. The interaction (V,H) associated to a graph E acts...... on the core F_E of the graph algebra C*(E). By describing a partial homeomorphism dual to (V,H) we find the fundamental structure theorems for C*(E), such as Cuntz–Krieger uniqueness theorem, as results concerning reversible noncommutative dynamics on F_E . We also provide a new approach to calculation of K...

  16. A heterogeneous graph-based recommendation simulator

    Energy Technology Data Exchange (ETDEWEB)

    Yeonchan, Ahn [Seoul National University; Sungchan, Park [Seoul National University; Lee, Matt Sangkeun [ORNL; Sang-goo, Lee [Seoul National University

    2013-01-01

    Heterogeneous graph-based recommendation frameworks have flexibility in that they can incorporate various recommendation algorithms and various kinds of information to produce better results. In this demonstration, we present a heterogeneous graph-based recommendation simulator which enables participants to experience the flexibility of a heterogeneous graph-based recommendation method. With our system, participants can simulate various recommendation semantics by expressing the semantics via meaningful paths like User Movie User Movie. The simulator then returns the recommendation results on the fly based on the user-customized semantics using a fast Monte Carlo algorithm.

  17. Integer sequence discovery from small graphs.

    Science.gov (United States)

    Hoppe, Travis; Petrone, Anna

    2016-03-11

    We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and six sequences were extended. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work.

  18. Integer sequence discovery from small graphs

    Science.gov (United States)

    Hoppe, Travis; Petrone, Anna

    2015-01-01

    We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and six sequences were extended. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work. PMID:27034526

  19. Assessing statistical significance in causal graphs.

    Science.gov (United States)

    Chindelevitch, Leonid; Loh, Po-Ru; Enayetallah, Ahmed; Berger, Bonnie; Ziemek, Daniel

    2012-02-20

    Causal graphs are an increasingly popular tool for the analysis of biological datasets. In particular, signed causal graphs--directed graphs whose edges additionally have a sign denoting upregulation or downregulation--can be used to model regulatory networks within a cell. Such models allow prediction of downstream effects of regulation of biological entities; conversely, they also enable inference of causative agents behind observed expression changes. However, due to their complex nature, signed causal graph models present special challenges with respect to assessing statistical significance. In this paper we frame and solve two fundamental computational problems that arise in practice when computing appropriate null distributions for hypothesis testing. First, we show how to compute a p-value for agreement between observed and model-predicted classifications of gene transcripts as upregulated, downregulated, or neither. Specifically, how likely are the classifications to agree to the same extent under the null distribution of the observed classification being randomized? This problem, which we call "Ternary Dot Product Distribution" owing to its mathematical form, can be viewed as a generalization of Fisher's exact test to ternary variables. We present two computationally efficient algorithms for computing the Ternary Dot Product Distribution and investigate its combinatorial structure analytically and numerically to establish computational complexity bounds.Second, we develop an algorithm for efficiently performing random sampling of causal graphs. This enables p-value computation under a different, equally important null distribution obtained by randomizing the graph topology but keeping fixed its basic structure: connectedness and the positive and negative in- and out-degrees of each vertex. We provide an algorithm for sampling a graph from this distribution uniformly at random. We also highlight theoretical challenges unique to signed causal graphs

  20. Identifying Codes on Directed De Bruijn Graphs

    Science.gov (United States)

    2015-08-27

    JOURNAL ARTICLE (POST PRINT) 3. DATES COVERED (From - To) JUN 2013 – AUG 2015 4. TITLE AND SUBTITLE IDENTIFYING CODES ON DIRECTED DE BRUIJN GRAPHS 5a...owner. 14. ABSTRACT For a directed graph G, a t-identifying code is a subset S ⊆ V (G) with the property that for each vertex v ∈ V (G) the set of...vertices of S reachable from v by a directed path of length at most t is both non-empty and unique. A graph is called t- identifiable if there exists a