We consider the complexity of the isomorphism relation on countable first-order structures with transitive automorphism groups. We use the theory of Borel reducibility of equivalence relations to show that the isomorphism problem for vertex-transitive graphs is as complicated as the isomorphism problem for arbitrary graphs and determine for which first-order languages the isomorphism problem for transitive countable structures is as complicated as it is for arbitrary countable structures. We then use these results to characterize the complexity (...) of the isometry relation for certain classes of homogeneous and ultrahomogeneous metric spaces. (shrink)

This paper deals with problems that vagueness raises for choices involving evaluative tradeoffs. I focus on a species of such choices, which I call ‘qualitative barrier cases.’ These are cases in which a qualitatively significant tradeoff in one evaluative dimension for a given improvement in another dimension could not make an option better all things considered, but a merely quantitative tradeoff for the given improvement might. Trouble arises, however, when one of the options constitutes a borderline case of an evaluative (...) kind. I argue that in such cases we can neither affirm nor deny that trading off losses in one evaluative dimension for gains in another yields a better outcome. Theoretically, this result provides a way to defuse an argument that has been presented by both Larry Temkin and Stuart Rachels that purports to show that the ‘better than’ relation is intransitive. Practically, it allows us to undermine the claim that rational agents are better off withholding their contribution to a public good in certain instances of the free-rider problem, and thus to take an important step towards solving these problems. (shrink)

We consider the classification problem for several classes of countable structures which are “vertex-transitive”, meaning that the automorphism group acts transitively on the elements. We show that the classification of countable vertex-transitive digraphs and partial orders are Borel complete. We identify the complexity of the classification of countable vertex-transitive linear orders. Finally we show that the classification of vertex-transitive countable tournaments is properly above \ in complexity.

In the thesis some combinatorial statements are analysed from the reverse mathematics point of view. Reverse mathematics is a research program, which dates back to the Seventies, interested in finding the exact strength, measured in terms of set-existence axioms, of theorems from ordinary non set-theoretic mathematics. After a brief introduction to the subject, an on-line (incremental) algorithm to transitively reorient infinite pseudo-transitive oriented graphs is defined. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is (...) computably true. Interval graphs and interval orders are the common theme of the second part of the thesis. A chapter is devoted to analyse the relative strength of different characterisations of countable interval graphs and to study the interplay between countable interval graphs and countable interval orders. In this context the theme of unique orderability of interval graphs arises, which is studied in the following chapter. The last chapter about interval orders inspects the strength of some statements involving the dimension of countable interval orders. The third part is devoted to the analysis of two theorems proved by Rival and Sands in 1980. The first principle states that each infinite graph contains an infinite subgraph such that each vertex of the graph is adjacent either to none, or to one or to infinitely many vertices of the subgraph. This statement, restricted to countable graphs, is proved to be equivalent to ACA_0 and hence to be stronger than Ramsey's theorem for pairs, despite the similarity of partial order with finite width contains an infinite chain such that each point of the poset is comparable either to none or to infinitely many points of the chain. For each k less than or equal to 3, the latter principle restricted to countable poset of width k is proved to be equivalent to ADS. Some complementary results are presented in the thesis. (shrink)

Given any finite graph, which transitive graphs approximate it most closely and how fast can we find them? The answer to this question depends on the concept of “closest approximation” involved. In [8,9] a qualitative concept of best approximation is formulated. Roughly, a qualitatively best transitive approximation of a graph is a transitive graph which cannot be “improved” without also going against the original graph. A quantitative concept of best approximation goes back at (...) least to [10]. A quantitatively best transitive approximation is a transitive graph that makes the minimal number of mistakes against the original graph. In other words, the sum of the edges that are removed from and are added to the original graph is minimal. (shrink)

We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other.

In the vertex pursuit game of cops and robbers on finite graphs, the cop has a winning strategy if and only if the graph admits a dominating order. Such graphs are called constructible in the graph theory literature. This equivalence breaks down for infinite graphs, and variants of the game have been proposed to reestablish partial connections between constructibility and being cop-win. We answer an open question of Lehner about one of these variants by giving examples of (...) weak cop-win graphs which are not constructible. We show that the index set of computable constructible graphs is Π11 hard and the index set of computable constructible locally finite graphs is Π40 hard. Finally, we give an example of a computable constructible graph for which every dominating order computes 0″. (shrink)

A topological index can be focused on uprising of a chemical structure into a real number. The degree-based topological indices have an active place among all topological indices. These topological descriptors intentionally associate certain physicochemical assets of the corresponding chemical compounds. Graph theory plays a very useful role in such type of research directions. The hex-derived networks have vast applications in computer science, physical sciences, and medical science, and these networks are constructed by hexagonal mesh networks. In this paper, (...) we determined the exact values of vertex-edge-degree-based topological descriptors for hex-derived networks HDN 1 p and HDN 2 p, which are generated by the hexagonal network of dimension p. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that (...) there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence (...) relation is computably isomorphic to a p-time equivalence relation with standard universe. (shrink)

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two (...) types of questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as (...) set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

Traditional spatial enabled grammars lack flexibility in specifying the spatial semantics of graphs. This paper describes a new graph grammar formalism called the multigranularity Coordinate Graph Grammar (mgCGG) for spatial graphs. Based on the Coordinate Graph Grammar (CGG), the mgCGG divides coordinates into two categories, physical coordinates and grammatical coordinates, where physical coordinates are the common coordinates in the real world, and grammatical coordinates describe the restrictions on the spatial semantics. In the derivation and reduction of the (...) mgCGG, the spatial matching conditions between nodes are evaluated on the basis of the grammatical coordinates, which can be obtained by the specified granularities. By adjusting the granularities, both qualitative and quantitative analyses for spatial semantics can be obtained, including the transition states between them. In addition, a new redex searching algorithm with polynomial time complexity is designed for the mgCGG. A running example of drawing a flowchart is given to illustrate a practical application of the mgCGG. Through a detailed comparison with related spatial-enabled grammars, it is found that the mgCGG has good performance in four critical aspects—the semantics processing mechanism, fault-tolerance, redex searching algorithm, and practical application—providing a flexible yet uniform way to specify spatial graphs and building a bridge between nonspatial and spatial grammars. (shrink)

We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinal $\mu$ , of cofinality $\omega$ , such that every $\mu^{+}$ -chromatic graph X on $\mu^{+}$ has an edge colouring c of X into $\mu$ colours for which every vertex colouring g of X into at most $\mu$ many colours has a g-colour class on which c takes every value. The paper also contains some generalisations of the above statement in which $\mu^{+}$ (...) is replaced by other cardinals < $\mu$. (shrink)

Any set x is uniquely specified by the graph of the membership relation on the set obtained by adjoining x to the transitive closure of x. Thus any operation on sets can be looked at as an operation on these graphs. We look at the operations of ordinal arithmetic of sets in this light. This turns out to be simplest for a modified ordinal arithmetic based on the Zermelo ordinals, instead of the usual von Neumann ordinals. In this (...) arithmetic, addition of sets corresponds to concatenating graphs, and multiplication corresponds to replacing each edge of a graph by a copy of another graph. Characterizations for the von Neumann case are also given. (shrink)

We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinalμ, of cofinalityω, such that everyμ+-chromatic graphXonμ+has an edge colouringcofXintoμcolours for which every vertex colouringgofXinto at mostμmany colours has ag-colour class on whichctakes every value.The paper also contains some generalisations of the above statement in whichμ+is replaced by other cardinals >μ.

There are many network topology designs that have emerged to fulfill the growing need for networks to provide a robust platform for a wide range of applications like running businesses and managing emergencies. Amongst the most famous network topology designs are star network, mesh network, hexagonal network, honeycomb network, etc. In a star network, a central computer is linked with various terminals and other computers over point-to-point lines. The other computers and terminals are directly connected to the central computer but (...) not to one another. As such, any failure in the central computer will result in a failure of the entire network and computers in star network will not be able to communicate. The star topology design can be represented by a graph where vertices represent the computer nodes and edges represent the links between the computer nodes. In this paper, we study the vertex-edge-based topological descriptor for a newly designed hexagon star network. (shrink)

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation (...) partly stems from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

Ideas from random graph theory are used to give an heuristic argument that associative memory structure depends discontinuously on pattern recognition ability. This argument suggests that there may be a certain minimal size for intelligent systems.

Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. (...) We show that CKDT is provable in ART0. Combining this with a result of Aharoni, Magidor, and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0. (shrink)

Let G be a connected graph with minimum degree δ G and vertex-connectivity κ G. The graph G is k -connected if κ G ≥ k, maximally connected if κ G = δ G, and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k -connected, maximally connected, or super-connected in terms of the number of edges, (...) the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k -connected, maximally connected, or super-connected are also presented. (shrink)

Peirce’s beta graphs are roughly equivalent to our first-order predicate logic. However, Bellucci and Pietarinen have recently argued that the beta graphs are not well-equipped to handle asymmetric relative terms. I survey four proposed solutions to the problem and find them all wanting. I offer a fifth solution according to which Peirce’s beta graphs function at three different levels of abstractness from natural language. I diagnose the problem of asymmetric relative terms as arising when we transition from the first to (...) the second level of abstractness. Making grammatical information encoded in natural language explicit at the first level of abstractness and interpreting graphs at the second level of abstractness as shorn of grammatical information resolves the problem. The solution is both well-motivated by Peirce’s own commitments and increases the expressiveness of the beta graphs. (shrink)

The number of edges in a shortest walk from one vertex to another vertex of a connected graph G is known as the distance between them. For a vertex x and an edge e = a b in G, the minimum number from distances of x with a and b is said to be the distance between x and e. A vertex x is said to distinguish two distinct edges e 1 and e 2 if (...) the distance between x and e 1 is different from the distance between x and e 2. A set X of vertices in a connected graph G is an edge metric generator for G if every two edges of G are distinguished by some vertex in X. The number of vertices in such a smallest set X is known as the edge metric dimension of G. In this article, we solve the edge metric dimension problem for certain classes of planar graphs. (shrink)

De Clercq (2012) proposes a strategy for denying purported graph-theoretic counterexamples to the Principle of the Identity of Indiscernibles (PII), by assuming that any vertex is contained by multiple graphs. Duguid (2016) objects that De Clercq fails to show that the relevant vertices are discernible. Duguid is right, but De Clercq’s strategy can be rescued. This note clarifies what assumptions about graph ontology are needed by De Clercq, and shows that, given those assumptions, any two vertices are (...) weakly discernible, and so are not counterexamples to the version of PII that requires only weak discernibility. (shrink)

Lachlan and Woodrow have completly classified the countable ultrahomogeneous graphs. We expand the language of graphs to include a new unary predicate. In this expanded language, ultrahomogeneous vertex 2-colorings of ultrahomogeneous graphs are classified.

Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f, w (...) = min d w, t, d w, s is referred as distance between f = t s an edge and w a vertex. d w, f 1 ≠ d w, f 2 implies that two edges f 1, f 2 ∈ E are resolved by node w ∈ V. A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, e dim Γ for a graph Γ. A set B of some nodes of Γ is a mixed metric generator if any two members of V ∪ E are resolved by some members of B. Such a set B with least cardinality is termed as mixed metric dimension, m dim Γ. In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph T n, m, line graph of dragon graph L T n, m, paraline graph of dragon graph L S T n, m, and line graph of line graph of dragon graph L L T n, m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs. (shrink)

Graph-based frames have been introduced as a logical framework which internalises an inherent boundary to knowability (referred to as ‘informational entropy’), due, e.g. to perceptual, evidential or linguistic limits. They also support the interpretation of lattice-based (modal) logics as hyper-constructive logics of evidential reasoning. Conceptually, the present paper proposes graph-based frames as a formal framework suitable for generalising Pawlak's rough set theory to a setting in which inherent limits to knowability exist and need to be considered. Technically, the (...) present paper establishes systematic connections between the first-order correspondents of Sahlqvist modal reduction principles on Kripke frames, and on the more general relational environments of graph-based and polarity-based frames. This work is part of a research line aiming at: (a) comparing and inter-relating the various (first-order) conditions corresponding to a given (modal) axiom in different relational semantics; (b) recognising when first-order sentences in the frame-correspondence languages of different relational structures encode the same ‘modal content’; (c) meaningfully transferring relational properties across different semantic contexts. The present paper develops these results for the graph-based semantics, polarity-based semantics, and all Sahlqvist modal reduction principles. As an application, we study well known modal axioms in rough set theory (such as those corresponding to seriality, reflexivity, and transitivity) on graph-based frames and show that, although these axioms correspond to different first-order conditions on graph-based frames, their intuitive meaning is retained. This allows us to introduce the notion of hyperconstructivist approximation spaces as the subclass of graph-based frames defined by the first-order conditions corresponding to the same modal axioms defining classical generalised approximation spaces, and to transfer the properties and the intuitive understanding of different approximation spaces to the more general framework of graph-based frames. The approach presented in this paper provides a base for systematically comparing and connecting various formal frameworks in rough set theory, and for the transfer of insights across different frameworks. (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 use methods of reverse mathematics to analyze the proof theoretic strength of a theorem involving the notion of coloring number. Classically, the coloring number of a graph $G=$ is the least cardinal $\kappa$ such that there is a well-ordering of $V$ for which below any vertex in $V$ there are fewer than $\kappa$ many vertices connected to it by $E$. We will study a theorem due to Komjáth and Milner, stating that if a graph is the (...) union of $n$ forests, then the coloring number of the graph is at most $2n$. We focus on the case when $n=1$. (shrink)

This study was designed to find out what scientists and science students actually do when they are reading familiar and unfamiliar graphs. This study provides rich details of the subtle changes in the ontologies of scientists and science students as they engage in the reading tasks assigned to them. In the course of the readers’ interpretation work, initially unspecified marks on paper are turned into objects with particular topologies that are said to correspond to specific features in the world. We (...) theorize this interpretive work as a transition of graphs from things to signs that come to stand for natural objects. Especially among physicists and theoretical ecologists, graphs enter new relations and become natural objects in their own right. (shrink)

LAS is a program that acquires augmented transition network (ATN) grammars. It requires as data sentences of the language and semantic network representatives of their meaning. In acquiring the ATN grammars, it induces the word classes of the language, the rules of formation for sentences, and the rules mapping sentences onto meaning. The induced ATN grammar can be used both for sentence generation and sentence comprehension. Critical to the performance of the program are assumptions that it makes about the relation (...) between sentence structure and surface structure (the graph deformation condition), about when word classes may be formed and when ATN networks may be merged, and about the structure of noun phrases. These assumptions seem to be good heuristics which are largely true for natural languages although they would not be true for many nonnatural languages. Provided these assumptions are satisfied LAS seems capable of learning any context‐free language. (shrink)

In this paper, a new method of quantitatively assessing continuity and discontinuity of visual attention is developed. The method is based on representing narrative information using graph theory. It is applicable to any type of narrative report. Since dream reports are often described as bizarre, and since bizarreness is partially characterized by discontinuities in plot, we chose to test our method on a set of dream data. Using specific criteria for identifying and arranging objects of visual attention, dream narratives (...) from 10 subjects were obtained and mapped onto graphs. The interrater reliabilities were 76% and 91% . Discontinuities in visual attention were quantified by plotting transitions from one part of a graph to another, which provided a spatiotemporal map of attention shifts within a narrative. This procedure was compared with other approaches to discontinuity and also applied to a set of 10 fantasy reports from the same subjects. The results showed that our method includes but transcends other approaches and has the capability to distinguish dream and fantasy reports. To our knowledge, the method provides the most rigorous and reliable measure to date of continuity and discontinuity of attention in narrative reports. (shrink)

We prove that any positive elementary (least fixed point) induction expressing the negation of transitive closure on finite nondirected graphs requires at least two recursion variables.

Continuous subgraph matching problem on dynamic graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including information retrieval and community detection. Specifically, given a query graph q, an initial graph G 0, and a graph update stream △ G i, the problem of continuous subgraph matching is to sequentially conduct all possible isomorphic subgraphs covering △ G i of q on G i. Since knowledge (...) graph is a directed labeled multigraph having multiple edges between a pair of vertices, it brings new challenges for the problem focusing on dynamic knowledge graph. One challenge is that the multigraph characteristic of knowledge graph intensifies the complexity of candidate calculation, which is the combination of complex topological and attributed structures. Another challenge is that the isomorphic subgraphs covering a given region are conducted on a huge search space of seed candidates, which causes a lot of time consumption for searching the unpromising candidates. To address these challenges, a method of subgraph-indexed sequential subdivision is proposed to accelerating the continuous subgraph matching on dynamic knowledge graph. Firstly, a flow graph index is proposed to arrange the search space of seed candidates in topological knowledge graph and an adjacent index is designed to accelerate the identification of candidate activation states in attributed knowledge graph. Secondly, the sequential subdivision of flow graph index and the transition state model are employed to incrementally conduct subgraph matching and maintain the regional influence of changed candidates, respectively. Finally, extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms. (shrink)

For each vertex of a simple polygon P an integer valued weight is given. We consider the path p1, p2, ..., pk in P which is created according to the following strategy: p1 is a designated start vertex s and pi+1 is obtained by choosing the vertex with smallest weight among all vertices visible from pi and different from p1, p2, ..., pi. If there is no such vertex the path is finished. This path is called (...) geometric lexicographic dead end path. We shall prove the problem of determining whether a distinguished vertex t of P is on the geometric lexicographic dead end path or not to be P-complete. (shrink)

Data-driven historiography of philosophy looks to objective modeling tools for illumination of the propagation of influence. While the system of David Lewis, the most influential philosopher of our time, raises historiographic puzzles to stymie conventional analytic methods, it proves amenable to data-driven analysis. A striking result is that Lewis only becomes the metaphysician of current legend following the midpoint of his career: his initial project is to frame a descriptive science of mind and meaning; the transition to metaphysics is a (...) rhetorically breathtaking escape from this program's (inevitable) collapse. Understanding this process both aids a more focused debate whether it counts as progress, and also presents novel affordances for partisans on both sides to learn from Lewis's right and wrong steps. (shrink)

Stability definitions for describing human behavior under conflict when coalitions may form are generalized within the Graph Model for Conflict Resolution and algebraic formulations of these definitions are provided to allow computer implementation. The more general definitions of coalitional stabilities relax the assumption of transitive graphs capturing movements under the control of decision makers, either independently or cooperatively, and allow the convenient expansion to the case of coalitions of the four basic individual stabilities consisting of Nash stability, general (...) metarationality, symmetric metarationality, and sequential stability. To permit the various coalitional stabilities to be efficiently calculated and conveniently encoded within a decision support system, algebraic expressions for the coalitional stabilities are provided in this research. Furthermore, a range of the theorems establish the mathematical credibility of employing the innovative algebraic approach to conflict resolution when coalitions are present. Finally, a conflict over the proposed exportation of bulk water from Lake Gisborne within the Canadian Province of Newfoundland and Labrador is modelled and analyzed to illustrate the practical application of the different coalitional stabilities and the strategic insights they provide. (shrink)

A graph’s entropy is a functional one, based on both the graph itself and the distribution of probability on its vertex set. In the theory of information, graph entropy has its origins. Hex-derived networks have a variety of important applications in medication store, hardware, and system administration. In this article, we discuss hex-derived network of type 1 and 2, written as HDN 1 n and HDN 2 n, respectively of order n. We also compute some degree-based (...) entropies such as Randić, ABC, and G A entropy of HDN 1 n and HDN 2 n. (shrink)

How many words—and which ones—are sufficient to define all other words? When dictionaries are analyzed as directed graphs with links from defining words to defined words, they reveal a latent structure. Recursively removing all words that are reachable by definition but that do not define any further words reduces the dictionary to a Kernel of about 10% of its size. This is still not the smallest number of words that can define all the rest. About 75% of the Kernel turns (...) out to be its Core, a “Strongly Connected Subset” of words with a definitional path to and from any pair of its words and no word's definition depending on a word outside the set. But the Core cannot define all the rest of the dictionary. The 25% of the Kernel surrounding the Core consists of small strongly connected subsets of words: the Satellites. The size of the smallest set of words that can define all the rest—the graph's “minimum feedback vertex set” or MinSet—is about 1% of the dictionary, about 15% of the Kernel, and part-Core/part-Satellite. But every dictionary has a huge number of MinSets. The Core words are learned earlier, more frequent, and less concrete than the Satellites, which are in turn learned earlier, more frequent, but more concrete than the rest of the Dictionary. In principle, only one MinSet's words would need to be grounded through the sensorimotor capacity to recognize and categorize their referents. In a dual-code sensorimotor/symbolic model of the mental lexicon, the symbolic code could do all the rest through recombinatory definition. (shrink)

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of (...) forbidden induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: –There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs.–Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f.Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.

We explore one aspect of the structure of a codified legal system at the national level using a new type of representation to understand the strong or weak dependencies between the various fields of law. In Part I of this study, we analyze the graph associated with the network in which each French legal code is a vertex and an edge is produced between two vertices when a code cites another code at least one time. We show that (...) this network distinguishes from many other real networks from a high density, giving it a particular structure that we call concentrated world and that differentiates a national legal system (as considered with a resolution at the code level) from small-world graphs identified in many social networks. Our analysis then shows that a few communities (groups of highly wired vertices) of codes covering large domains of regulation are structuring the whole system. Indeed we mainly find a central group of influent codes, a group of codes related to social issues and a group of codes dealing with territories and natural resources. The study of this codified legal system is also of interest in the field of the analysis of real networks. In particular we examine the impact of the high density on the structural characteristics of the graph and on the ways communities are searched for. Finally we provide an original visualization of this graph on an hemicyle-like plot, this representation being based on a statistical reduction of dissimilarity measures between vertices. In Part II (a following paper) we show how the consideration of the weights attributed to each edge in the network in proportion to the number of citations between two vertices (codes) allows deepening the analysis of the French legal system. (shrink)

A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the (...) neighbors of a vertex. We show that, if A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs. (shrink)

For a graph G, its variable sum exdeg index is defined as SEI a G = ∑ x y ∈ E G a d x + a d y, where a is a real number other than 1 and d x is the degree of a vertex x. In this paper, we characterize all trees on n vertices with first three maximum and first three minimum values of the SEI a index. Also, we determine all the trees of (...) order n with given diameter d and having first three largest values of the SEI a index. (shrink)

In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: It is very natural to define in this logic two negations, weak negation as (...) failure to verify a sentence, and strong negation as the existence of a falsifying strategy: One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc. (shrink)

Knowledge representation and reasoning (KRR) is a fundamental area in artificial intelligence (AI) research, focusing on encoding world knowledge as logical formulae in ontologies. This formalism enables logic-based AI systems to deduce new insights from existing knowledge. Within KRR, description logics (DLs) are a prominent family of languages to represent knowledge formally. They are decidable fragments of first-order logic, and their models can be visualized as edge- and vertex-labeled directed binary graphs. DLs facilitate various reasoning tasks, including checking the (...) satisfiability of statements and deciding entailment. However, a significant challenge arises in the computation of models of DL ontologies in the context of explaining reasoning results. Although existing algorithms efficiently compute models for reasoning tasks, they usually do not consider aspects of human cognition, leading to models that may be less effective for explanatory purposes. This paper tackles this challenge by proposing an approach to enhance the intelligibility of models of DL ontologies for users. By integrating insights from cognitive science and philosophy, we aim to identify key graph properties that make models more accessible and useful for explanation. (shrink)

We consider three problems concerning alpha conversion of closed terms (combinators). (1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables. (2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N. (3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way. We obtain the following results. (...) (1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs. (2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2). (3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given. There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand. (shrink)