Graph theory is a specific concept that has numerous applications throughout many industries. Despite the advancement of this technique, graph theory can still yield ambiguous and imprecise results. In order to cut down on these indeterminate factors, neutrosophic logic has emerged as an applicable solution that is gaining significant attention in solving many real-life decision-making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistency, and indeterminacy. However, empirical research on this specific graph set is lacking. Neutrosophic (...) Graph Theory and Algorithms is a collection of innovative research on the methods and applications of neutrosophic sets and logic within various fields including systems analysis, economics, and transportation. While highlighting topics including linear programming, decision-making methods, and homomorphism, this book is ideally designed for programmers, researchers, data scientists, mathematicians, designers, educators, researchers, academicians, and students seeking current research on the various methods and applications of graph theory. (shrink)

The mathematical field of graph theory has recently been used to provide counterexamples to the Principle of the Identity of Indiscernibles. In response to this, it has been argued that appeal to relations between graphs allows the Principle to survive the counterexamples. In this paper, I aim to show why that proposal does not succeed.

Studies to neutrosophic graphs happens to be not only innovative and interesting, but gives a new dimension to graph theory. The classic coloring of edge problem happens to give various results. Neutrosophic tree will certainly find lots of applications in data mining when certain levels of indeterminacy is involved in the problem. Several open problems are suggested.

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of (...) each topic. The ability of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (shrink)

This book covers a wide variety of topics in combinatorics and graph theory.

Numerical simulations of coupled map lattices (CMLs) and other complex model systems show an enormous phenomenological variety that is difficult to classify and understand. It is therefore desirable to establish analytical tools for exploring fundamental features of CMLs, such as their stability properties. Since CMLs can be considered as graphs, we apply methods of spectral graph theory to analyze their stability at locally unstable fixed points for different updating rules, different coupling scenarios, and different types of neighborhoods. (...) Numerical studies are found to be in excellent agreement with our theoretical results. (shrink)

For digraphs G, we write V(G) for the set of all vertices of G, and E(G) for the set of all edges of G. A digraph on a set E is a digraph G where V(G) = E.

AimsAlcohol consumption could lead to a series of health problems and social issues. In the current study, we investigated the resting-state functional brain networks of healthy volunteers before and after drinking through graph-theory analysis, aiming to ascertain the effects of acute alcohol intake on topology and information processing mode of the functional brain networks.Materials and methodsThirty-three healthy volunteers were enrolled in this experiment. Each volunteer accepted alcohol breathalyzer tests followed by resting-state magnetic resonance imaging at three time points: (...) before drinking, 0.5 h after drinking, and 1 h after drinking. The data obtained were grouped based on scanning time into control group, 0.5-h group and 1-h group, and post-drinking data were regrouped according to breath alcohol concentration (BrAC) into relative low BrAC group (A group; 0.5-h data, n = 17; 1-h data, n = 16) and relative high BrAC group (B group; 0.5-h data, n = 16; 1-h data, n = 17). The graph-theory approach was adopted to construct whole-brain functional networks and identify the differences of network topological properties among all the groups.ResultsThe network topology of most groups was altered after drinking, with the B group presenting the most alterations. For global network measures, B group exhibited increased global efficiency, Synchronization, and decreased local efficiency, clustering coefficient, normalized clustering coefficient, characteristic path length, normalized characteristic path length, as compared to control group. Regarding nodal network measures, nodal clustering coefficient and nodal local efficiency of some nodes were lower in B group than control group. These changes suggested that the network integration ability and synchrony improved, while the segregation ability diminished.ConclusionThis study revealed the effects of acute alcohol intake on the topology and information processing mode of resting-state functional brain networks, providing new perceptions and insights into the effects of alcohol on the brain. (shrink)

Various methods have been employed to investigate different aspects of the brain activity modulation related to the performance of a cycling task. In our study we examined how functional connectivity and brain network efficiency varied during an endurance cycling task. To this purpose, we reconstructed EEG signals at source level: we computed current densities in 28 anatomical regions of interest (ROIs) through the eLORETA algorithm, then we calculated the Lagged Coherence of the 28 current density signals to define the adjacency (...) matrix. To quantify changes of functional network efficiency during an exhaustive cycling task, we computed three graph theoretical indices: local efficiency (LE), global efficiency (GE) and Density (D) in two different frequency bands, Alpha and Beta bands, that indicate alertness processes and motor binding/fatigue respectively. This analysis was conducted for six different task intervals: pre-cycling, initial, intermediate and final stages of cycling, active recovery and passive recovery. Fourteen participants performed an incremental cycling task with simultaneous EEG recording and RPE monitoring to detect participants’ exhaustion. LE remained constant during the endurance cycling task in both bands. Therefore, we speculate that fatigue processes did not affect segregated neural processing. We observed an increase of GE in the Alpha band only during cycling, that could be due to greater alertness processes and preparedness to stimuli during exercise. Conversely, although D did not change significantly over time in the Alpha band, its general reduction in the Beta bands during cycling could be interpreted within the framework of the neural efficiency hypothesis, which posits a reduced neural activity for expert/automated performances. We argue that the use of graph theoretical indices represents a clear methodological advancement in studying endurance performance. (shrink)

The seminal book on graph theory by Dénes Kőnig, published in the year 1936, collected notions and results from precursory works from the mid to late nineteenth century by Hamilton, Cayley, Sylvester and others. More importantly, Kőnig himself contributed many of his own results that he had obtained in the more than twenty years that he had been working on this subject matter. What is noteworthy is the fact that the fundamentals of what he calls directed graphs are (...) taken almost exhaustively from Paul Hertz' 1922 article on structural reasoning about sentences of the form a→b. This is not a fact that is well known in logical circles, even though Kőnig fully acknowledges this in his book. In view of the numerous trends in the recent decades to describe and explicate logical matters by means of graphs, the fact that it was Hertz' foundation of structural reasoning that informed basic notions of graph theory in the first place is highly significant. The main goal of this paper is to summarize Hertz' article and demonstrate how Kőnig integrates the notions and results presented therein in his book. This is followed by an exposition of how and when Hertz' results were reinvented in terms of graph theory. A critical discussion of the opinion expressed by both Hertz and Kőnig that the more general sentences of the form (a1,…,an)→b, introduced by Hertz in a companion article in 1923, cannot be interpreted by graphs concludes this paper. (shrink)

Objective: Cognitive impairment is a common neurological complication in patients with end-stage renal disease undergoing maintenance hemodialysis. Brain network analysis based on graph theory is a promising tool for studying CI. Therefore, the purpose of this study was to analyze the changes of functional brain networks in patients on MHD with and without CI by using graph theory and further explore the underlying neuropathological mechanism of CI in these patients.Methods: A total of 39 patients on MHD (...) and 25 healthy controls matched for age, sex, and years of education were enrolled in the study. Resting-state functional magnetic resonance imaging and T1-weighted high-resolution anatomical data were obtained, and functional brain networks for each subject were constructed. The brain network parameters at the global and regional levels were calculated, and a one-way analysis of covariance was used to compare the differences across the three groups. The associations between the changed graph-theory parameters and cognitive function scores in patients on MHD were evaluated using Spearman correlation analysis.Results: Compared with HCs, the global parameters [sigma, gamma, and local efficiency ] in both patient groups decreased significantly. The clustering coefficient in patients with CI was significantly lower than that in the other two groups. The regional parameters were significantly lower in the right superior frontal gyrus, dorsolateral and gyrus rectus of patients with CI than those of patients without CI; however the nodal local efficiency in the left amygdala was significantly increased. The global Cp and regional parameters in the three brain regions were significantly correlated with the cognitive function scores.Conclusion: This study confirmed that the topology of the functional brain network was disrupted in patients on MHD with and without CI and the disruption of brain network was more severe in patients with CI. The abnormal brain network parameters are closely related to cognitive function in patients on MHD. (shrink)

We construct a collection of new topological Ramsey spaces of trees. It is based on the Halpern-Läuchli theorem, but different from the Milliken space of strong subtrees. We give an example of its application by proving a partition theorem for profinite graphs.

I examine the adequacy of the causal graph-structural equations approach to causation for modeling biological mechanisms. I focus in particular on mechanisms with complex dynamics such as the PER biological clock mechanism in Drosophila. I show that a quantitative model of this mechanism that uses coupled differential equations – the well-known Goldbeter model – cannot be adequately represented in the standard causal graph framework, even though this framework does permit causal cycles. The reason is that the model contains (...) dynamical information about the mechanism that concerns causal properties but that does not correspond to variables that could be subject to independent interventions. Thus, a representation of the mechanisms as a causal structural model necessarily suppresses causally relevant information. (shrink)

Since then we have been engaged in the development of such results of greater relevance to mathematical practice. In January, 1997 we presented some new results of this kind involving what we call “jump free” classes of finite functions. This Jump Free Theorem is treated in section 2.

Volume 500, 2009 On the Infrared Problem for the Dressed Non-Relativistic Electron in a Magnetic Field Laurent Amour, ...

It is shown that complex adaptations are best modelled as discrete processes represented on directed weighted graphs. Such a representation captures the idea that problems of adaptation in evolutionary biology are problems in a discrete space, something that the conventional representations using continuous adaptive landscapes does not. Further, this representation allows the utilization of well-known algorithms for the computation of several biologically interesting results such as the accessibility of one allele from another by a specified number of point mutations, the (...) accessibility of alleles at a local maximum of fitness, the accessibility of the allele with the globally maximum fitness, etc. A reduction of a model due to Kauffman and Levin to such a representation is explicitly carried out and it is shown how this reduction clarifies the biological questions that are of interest. (shrink)

In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph's nodes. Such theories, which we call annotation theories^ can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including (...) satisfiability, querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPTime- or co-NPTime-complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21]. (shrink)

We sketch the ideas behind the use of chromatic numbers in establishing descriptive set-theoretic dichotomy theorems.

This book synthesizes Jacques Derrida’s hauntology and spectrality with affect theory, in order to create a rhetorical framework analyzing the felt absences and hauntings of written and oral texts. The book opens with a history of hauntology, spectrality, and affect theory and how each of those ideas have been applied. The book then moves into discussing the unique elements of the rhetorical framework known as the rhetorrectional situation. Three case studies taken from the Christian tradition, serve to demonstrate (...) how spectral rhetoric works. The first is fictional, C.S. Lewis ’The Great Divorce. The second is non-fiction, Tim Jennings ’The God Shaped Brain. The final one is taken from homiletics, Bishop Michael Curry’s royal wedding 2018 sermon. After the case studies conclusion offers the reader a summary and ideas future applications for spectral rhetoric. (shrink)

Modeling mechanisms is central to the biological sciences – for purposes of explanation, prediction, extrapolation, and manipulation. A closer look at the philosophical literature reveals that mechanisms are predominantly modeled in a purely qualitative way. That is, mechanistic models are conceived of as representing how certain entities and activities are spatially and temporally organized so that they bring about the behavior of the mechanism in question. Although this adequately characterizes how mechanisms are represented in biology textbooks, contemporary biological research practice (...) shows the need for quantitative, probabilistic models of mechanisms, too. In this paper we argue that the formal framework of causal graph theory is well-suited to provide us with models of biological mechanisms that incorporate quantitative and probabilistic information. On the ba-sis of an example from contemporary biological practice, namely feedback regulation of fatty acid biosynthesis in Brassica napus, we show that causal graph theoretical models can account for feedback as well as for the multi-level character of mechanisms. However, we do not claim that causal graph theoretical representations of mechanisms are advantageous in all respects and should replace common qualitative models. Rather, we endorse the more balanced view that causal graph theoretical models of mechanisms are useful for some purposes, while being insufficient for others. (shrink)

We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).

Analogues of Ramsey’s Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the author’s recent result for the triangle-free Henson graph, we prove (...) that for each [Formula: see text], the k-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey’s Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker. (shrink)

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math.38(1) (1971) 69–83] and denoted H3, is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.I, eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] (...) and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica26(2) (2006) 183–205], the Ramsey theory of H3 had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin.2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math.185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph G, there is a finite number T(G) such that for any coloring of all copies of G in H3 into finitely many colors, there is a subgraph of H3 which is again universal homogeneous triangle-free in which the coloring takes no more than T(G) colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code H3 and the development of their Ramsey theory. (shrink)

We generalize the Unstable Formula Theorem characterization of stable theories from Shelah [11], that a theory T is stable just in case any infinite indiscernible sequence in a model of T is an indiscernible set. We use a generalized form of indiscernibles from [11], in our notation, a sequence of parameters from an L-structure M, , indexed by an L′-structure I is L′-generalized indiscernible inM if qftpL′=qftpL′ implies tpL=tpL for all same-length, finite ¯,j from I. Let Tg be the (...) theory of linearly ordered graphs in the language with signature Lg={<,R}. Let Kg be the class of all finite models of Tg. We show that a theory T has NIP if and only if any Lg-generalized indiscernible in a model of T indexed by an Lg-structure with age equal to Kg is an indiscernible sequence. (shrink)

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

We introduce a framework for a graph-theoretic analysis of the semantic paradoxes. Similar frameworks have been recently developed for infinitary propositional languages by Cook and Rabern, Rabern, and Macauley. Our focus, however, will be on the language of first-order arithmetic augmented with a primitive truth predicate. Using Leitgeb’s notion of semantic dependence, we assign reference graphs (rfgs) to the sentences of this language and define a notion of paradoxicality in terms of acceptable decorations of rfgs with truth values. It (...) is shown that this notion of paradoxicality coincides with that of Kripke. In order to track down the structural components of an rfg that are responsible for paradoxicality, we show that any decoration can be obtained in a three-stage process: first, the rfg is unfolded into a tree, second, the tree is decorated with truth values (yielding a dependence tree in the sense of Yablo), and third, the decorated tree is re-collapsed onto the rfg. We show that paradoxicality enters the picture only at stage three. Due to this we can isolate two basic patterns necessary for paradoxicality. Moreover, we conjecture a solution to the characterization problem for dangerous rfgs that amounts to the claim that basically the Liar- and the Yablo graph are the only paradoxical rfgs. Furthermore, we develop signed rfgs that allow us to distinguish between ‘positive’ and ‘negative’ reference and obtain more fine-grained versions of our results for unsigned rfgs. (shrink)

In Ref. 1 we have considered the finite-dimensional quantum mechanics. There the quantum mechanical space of states wasV=C r. It is known that the second quantization of this space is the space of square-summable functions of finite number of variables(L 2(Rr,dx)) (Segal isomorphism). Creation and annihilation operators were introduced in Ref. 1, and the former coincided with the usual position and momentum operators in the conventional quantum mechanics. In this paper we shall investigate the spectral properties of field operators. (...) We shall show that the isomorphism between the exponential ofV andL 2(Rr,dx) can be understood as the decomposition by generalized eigenvectors of field operators (“Fourier transform”). (shrink)

The present paper is the first part of a work which follows up on H. Kummer: “A constructive approach to the foundations of quantum mechanics,”Found. Phys. 17, 1–63 (1987). In that paper we deduced the JB-algebra structure of the space of observables (=detector space) of quantum mechanics within an axiomatic theory which uses the concept of a filter as primitive under the restrictive assumption that the detector space is finite-dimensional. This additional hypothesis will be dropped in the present paper.It (...) turns out that the relevant mathematics for our approach to a quantum mechanical system with infinite-dimensional detector space is the noncommutative spectral theory of Alfsen and Shultz.We start off with the same situation as in the previous paper (cf. Sects. 1 and 2 of the present paper). By postulating four axioms (Axioms S, DP, R, and SP of Sec. 3), we arrive in a natural way at the mathematical setting of Alfsen and Shultz, which consists of a dual pair of real ordered linear spaces 〈Y, M〉: A base norm space, called the strong source space (which, however, in slight contrast to the setting of Alfsen and Shultz, is not 1-additive) and an order unit space, called the weak detector space, which is the norm and order dual space of Y. The last section of part I contains the guiding example suggested by orthodox quantum mechanics. We observe that our axioms are satisfied in this example. In the second part of this work (which will appear in the next issue of this journal) we shall postulate three further axioms and derive the JB-algebra structure of quantum mechanics. (shrink)

We study model companions of theories extending the graph axioms. First we prove general results concerning the existence of the model companion. Then, by applying these results to the case of graphs, we give a series of companionable and non‐companionable examples.

In this paper, we analyze and discuss Schopenhauer’s n-term diagrams for eristic dialectics from a graph-theoretical perspective. Unlike logic, eristic dialectics does not examine the validity of an isolated argument, but the progression and persuasiveness of an argument in the context of a dialogue or even controversy. To represent these dialogue situations, Schopenhauer created large maps with concepts and Euler-type diagrams, which from today’s perspective are a specific form of graphs. We first present the original method with Euler-type diagrams, (...) then give the most important graph-theoretical definitions, then discuss Schopenhauer’s diagrams graph-theoretically and finally give an example of how the graphs or diagrams can be used to analyze dialogues. (shrink)