Search

Various Monte Carlo techniques are used to determine the complete phase diagrams of the square-well model for the attractive ranges λ=1.15 and λ=1.25. The results for the latter case are in agreement with earlier Monte Carlo simulations for the fluid-fluid coexistence curve and yield new results for the liquidus-solidus lines. Our results for λ=1.15 are new. We find that the fluid-fluid critical point is metastable for both cases, with the case λ=1.25 being just below the threshold value for metastability. We compare our results with prior studies and with experimental results for the γII-crystallin. [ABSTRACT FROM AUTHOR]

Teachers should possess a robust knowledge of graph interpretation in a world that requires increasingly scientific citizens. This study aimed to investigate teachers' knowledge of interpreting a context-based line graph, by understanding the types of difficulties teachers have in interpreting such graphs. The study also sought to determine whether there were gender differences in teachers' graph interpretation skills and determine whether these interpretation skills were different among teachers with varying teaching experiences. Sixty-one teachers from ten districts in one Indonesian province participated in this study. Empirically derived items were developed to identify the teacher's conceptual understanding of line graphs with Curcio's (Journal for Research in Mathematics Education, 18(5), 382-393, 1987) level of interpretation applied to explain the difficulties encountered. This study revealed that most of the teachers had difficulty answering questions that required 'reading beyond the data'. Specifically, these teachers interpreted the graph as an iconic representation of a real event rather than an abstract representation of data (i.e., speed vs. time). Performance differences in teachers' understanding of the graph were dependent on the grade level they taught, with differences especially evident in the interpretation of moderate and difficult items. There were no differences in teachers' understanding by gender or years of teaching experience. The results highlight the importance of focusing on teacher professional development centering on teachers' knowledge of graph comprehension. [ABSTRACT FROM AUTHOR]

This paper studies two approaches to constructing control charts for linguistic data. Linguistic data can provide more information than the binary classification used in control charts by attributes. A generic approach for constructing attribute control charts using linguistic data is described. Several methods for calculating the values representing sample means, and for determining the centre line and the control limits are presented. [ABSTRACT FROM AUTHOR]

This paper presents a review of the exact formulae for control limits for P charts and C charts. Also presented are appropriate graphical methods so that these limits may be easily evaluated. The use of the exact methods, given appropriate tables and/or curves, is no more difficult than the approximate methods which are prevalent in the literature. This note is not intended to criticize the approximate techniques which have been used; rather it is intended to illustrate the use of existing theory whereby the errors of approximation may be eliminated. [ABSTRACT FROM AUTHOR]

We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. We give some examples where the random graph is dense and converges a.s. in the sense of graph limit theory, but also an example where a.s. every graph limit is the limit of some subsequence. Another example is sparse and yields convergence to a non-integrable generalized graphon defined on (0,∞). [ABSTRACT FROM AUTHOR]

Given a bipartite graph G=(A∪B,E) with strict preference lists and given an edge e∗∈E, we ask if there exists a popular matching in G that contains e∗. We call this the popular edge problem. A matching M is popular if there is no matching M′ such that the vertices that prefer M′ to M outnumber those that prefer M to M′. It is known that every stable matching is popular; however G may have no stable matching with the edge e∗. In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e∗, then there is either a stable matching that contains e∗ or a dominant matching that contains e∗. This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n=|A|+|B|. [ABSTRACT FROM AUTHOR]

Toric surface patch is the multi‐sided generalization of classical Bézier surface patch. Geometric continuity of the parametric surface patches plays a crucial role in geometric modeling. In this paper, the necessary and sufficient conditions of curvature continuity between toric surface patches are illustrated with the theory of toric degeneration. Furthermore, some practical sufficient conditions of curvature continuity of toric surface patches are also developed. [ABSTRACT FROM AUTHOR]

We present a novel method to construct subdivision stencils near extraordinary vertices with limit surfaces having optimal bounded curvature at extraordinary positions. With the proposed method, subdivision stencils for newly inserted and updated vertices near extraordinary vertices are first constructed to ensure subdivision with G1 continuity and bounded curvature at extraordinary positions. The remaining degrees of freedom of the constructed subdivision stencils are further used to optimize the eigenbasis functions corresponding to the subsubdominant eigenvalues of the subdivision with respect to G2 continuity constraints. We demonstrate the method by replacing subdivision stencils near extraordinary vertices for Catmull‐Clark subdivision and compare the results with the original Catmull‐Clark subdivision and previous tuning schemes known with small curvature variation near extraordinary positions. The results show that the proposed method produces subdivision schemes with better or comparable curvature behavior around extraordinary vertices with comparatively simple subdivision stencils. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring and M be an R-module, and let I(R)∗ be the set of all nontrivial ideals of R. The M-intersection graph of ideals of R, denoted by GM(R), is a graph with the vertex set I(R)∗, and two distinct vertices I and J are adjacent if and only if IM∩JM≠{0}. For every multiplication R-module M, the diameter and the girth of GM(R) are determined. Among other results, we prove that if M is a faithful R-module and the clique number of GM(R) is finite, then R is a semilocal ring. We denote the ℤn-intersection graph of ideals of the ring ℤm by Gn(ℤm), where n,m≥2 are integers and ℤn is a ℤm-module. We determine the values of n and m for which Gn(ℤm) is perfect. Furthermore, we derive a sufficient condition for Gn(ℤm) to be weakly perfect. [ABSTRACT FROM AUTHOR]

The spectral p -norm of r -matrices generalizes the spectral 2-norm of 2-matrices. In 1911 Schur gave an upper bound on the spectral 2-norm of 2-matrices, which was extended in 1934 by Hardy, Littlewood, and Pólya to r -matrices. Recently, Kolotilina, and independently the author, strengthened Schur's bound for 2-matrices. The main result of this paper extends the latter result to r -matrices, thereby improving the result of Hardy, Littlewood, and Pólya. The proof is based on combinatorial concepts like r-partite r-matrix and symmetrant of a matrix, which appear to be instrumental in the study of the spectral p -norm in general. Thus, another application shows that the spectral p -norm and the p -spectral radius of a symmetric nonnegative r -matrix are equal whenever p ≥ r . This result contributes to a classical area of analysis, initiated by Mazur and Orlicz back in 1930. Additionally, a number of bounds are given on the p -spectral radius and the spectral p -norm of r -matrices and r -graphs. [ABSTRACT FROM AUTHOR]

In this note we characterize, within the framework of the theory of finite set, those categories of graphs that are algebraic universal in the sense that every concrete category fully embeds in them. The proof of the characterization is based on the sparse–dense dichotomy and its model theoretic equivalent. [ABSTRACT FROM AUTHOR]

In the Lorentzian product G n × R 1 , we give a comparison theorem between the f -volume of an entire f -maximal graph and the f -volume of the hyperbolic H r + under the condition that the gradient of the function defining the graph is bounded away from 1. This condition comes from an example of non-planar entire f -maximal graph in G n × R 1 and is equivalent to the hyperbolic angle function of the graph being bounded. As a consequence, we obtain a Calabi–Bernstein type theorem for f -maximal graphs in G n × R 1 . [ABSTRACT FROM AUTHOR]

Consider a set of mobile robots placed on distinct nodes of a discrete, anonymous, and bidirectional ring. Asynchronously, each robot takes a snapshot of the ring, determining the size of the ring and which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or not. In the first case, it performs the computed move, eventually. This model of computation is known as Look- Compute- Move. The computation depends on the required task. In this paper, we solve both the well-known Gathering and Exclusive Searching tasks. In the former problem, all robots must simultaneously occupy the same node, eventually. In the latter problem, the aim is to clear all edges of the graph. An edge is cleared if it is traversed by a robot or if both its endpoints are occupied. We consider the exclusive searching where it must be ensured that two robots never occupy the same node. Moreover, since the robots are oblivious, the clearing is perpetual, i.e., the ring is cleared infinitely often. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a characterization of the initial configurations that permit the resolution of the problems under very weak assumptions. More precisely, we provide a full characterization (except for few pathological cases) of the initial configurations for which gathering can be solved. The algorithm relies on the necessary assumption of the local-weak multiplicity detection. This means that during the Look phase a robot detects also whether the node it occupies is occupied by other robots, without acquiring the exact number. For the exclusive searching, we characterize all (except for few pathological cases) aperiodic configurations from which the problem is feasible. We also provide some impossibility results for the case of periodic configurations. [ABSTRACT FROM AUTHOR]

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. [ABSTRACT FROM AUTHOR]

We present a novel approach for optimizing acoustic parameters using sensitivity analysis for computer-aided design and analysis of architectural models. Our approach builds on recent low-dispersion wave-based acoustic solvers that can accurately compute the pressure field in large models. We present an efficient technique to compute the gradient of the pressure field using automatic differentiation and combine that with a quasi-Newtonian optimization method to automatically compute the optimal material properties. We highlight the performance on many complex CAD models to optimize the strength and clarity acoustic parameters, and thereby improve the acoustic characteristics of large models. To the best of our knowledge, this is the first practical and accurate approach for acoustic material optimization of large indoor CAD models. [ABSTRACT FROM AUTHOR]

We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as $$\{0,\frac{1}{2}\}$$ -Chvátal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver. [ABSTRACT FROM AUTHOR]

A vague graph is a generalized structure of a fuzzy graph that gives more precision, flexibility and compatibility to a system when compared with systems that are designed using fuzzy graphs. In this paper, we defined the notions of product and complete product vague graphs. We investigated some properties of union, join and complement on product vague graphs and introduced the multiplication of the product vague graphs. Finally we give an application of product vague graphs. Product and complete product vague graphs are highly utilized by computer science, geometry, algebra, number theory and operation research. Likewise, these properties will also be helpful to study large vague graph as a combination of small, vague graphs and to derive its properties from those of the smaller ones. [ABSTRACT FROM AUTHOR]

Many networks can be modeled as signed graphs. These include social networks, and relationships/interactions networks. Detecting sub-structures in such networks helps us understand user behavior, predict links, and recommend products. In this paper, we detect dense sub-structures from a signed graph, called quasi antagonistic communities ( QACs). An antagonistic community consists of two groups of users expressing positive relationships within each group but negative relationships across groups. Instead of requiring complete set of negative links across its groups, a QAC allows a small number of inter-group negative links to be missing. We propose an algorithm, Mascot, to find all maximal quasi antagonistic communities ( MQACs). Mascot consists of two stages: pruning and enumeration stages. Based on the properties of QAC, we propose four pruning rules to reduce the size of candidate graphs in the pruning stage. We use an enumeration tree to enumerate all strongly connected subgraphs in a top-down fashion in the second stage before they are used to construct MQACs. We have conducted extensive experiments using synthetic signed graphs and two real networks to demonstrate the efficiency and accuracy of the Mascot algorithm. We have also found that detecting MQACs helps us to predict the signs of links. [ABSTRACT FROM AUTHOR]

A graph G is almost hypohamiltonian if G is non-hamiltonian, there exists a vertex w such that [ABSTRACT FROM AUTHOR]

We study biplane graphs drawn on a finite point set $$S$$ in the plane in general position. This is the family of geometric graphs whose vertex set is $$S$$ and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges. [ABSTRACT FROM AUTHOR]

A complete classification is given of pentavalent symmetric graphs of order $30p$, where $p\ge 5$ is a prime. It is proved that such a graph ${\Gamma }$ exists if and only if $p=13$ and, up to isomorphism, there is only one such graph. Furthermore, ${\Gamma }$ is isomorphic to $\mathcal{C}_{390}$, a coset graph of PSL(2, 25) with ${\sf Aut}\, {\Gamma }=\mbox{PSL(2, 25)}$, and ${\Gamma }$ is 2-regular. The classification involves a new 2-regular pentavalent graph construction with square-free order. [ABSTRACT FROM PUBLISHER]

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}G$ be a graph and ${{\tau }}$ be an assignment of nonnegative thresholds to the vertices of $G$. A subset of vertices, $D$, is an irreversible dynamic monopoly of $(G, \tau )$ if the vertices of $G$ can be partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$ and, for all $i$ with $0 \leq i \leq k-1$, each vertex $v$ in $D_{i+1}$ has at least $\tau (v)$ neighbours in the union of $D_0, D_1, \ldots, D_i$. Dynamic monopolies model the spread of influence or propagation of opinion in social networks, where the graph $G$ represents the underlying network. The smallest cardinality of any dynamic monopoly of $(G,\tau )$ is denoted by $\mathrm{dyn}_{\tau }(G)$. In this paper we assume that the threshold of each vertex $v$ of the network is a random variable $X_v$ such that $0\leq X_v \leq \deg _G(v)+1$. We obtain sharp bounds on the expectation and the concentration of $\mathrm{dyn}_{\tau }(G)$ around its mean value. We also obtain some lower bounds for the size of dynamic monopolies in terms of the order of graph and expectation of the thresholds. [ABSTRACT FROM PUBLISHER]

The aim of this paper is to extend the applicability of the incomplete oblique projections method (IOP) previously introduced by the authors for solving inconsistent linear systems to the box constrained case. The new algorithm employs incomplete projections onto the set of solutions of the augmented system Ax − r = b, together with the box constraints, based on a scheme similar to the one of IOP, adding the conditions for accepting an approximate solution in the box. The theoretical properties of the new algorithm are analyzed, and numerical experiences are presented comparing its performance with some well-known methods. [ABSTRACT FROM AUTHOR]

Usually, the plans of the utility network have been incorporated into planning documents as basic diagrams that establish a design and principle of estimated dimensions, principle that will later be developed technically and with absolute precision in a document not pertaining to the actual urban planning document, often drafted by specialized engineers and not by urban planning technicians. However, increasingly stringent conditioning factors, both in terms of how space should be occupied and the quantity and quality in the design of these utility networks, force us to deal with this as another factor determining urban planning and not, as used to happen, as a simple annex that can developed "a posteriori". The present article studies and reflects on the evolution of the graphic representation of utility networks in urban planning plans. It is based on the analysis of a significant enough sample performed under scientific criteria from assumable field work, sufficiently indicative and representative and which spans a significant period in time. [ABSTRACT FROM AUTHOR]

In Benjamini and Schramm [] introduced the notion of distributional limit of a sequence of graphs with uniformly bounded valence and studied such limits in the case that the involved graphs are planar. We investigate distributional limits of sequences of Riemannian manifolds with bounded curvature which satisfy a quasi-conformal condition. We then apply our results to somewhat improve Benjamini's and Schramm's original result on the recurrence of the simple random walk on limits of planar graphs. For instance, as an application we give a proof of the fact that for graphs in an expander family, the genus of each graph is bounded from below by a linear function of the number of vertices. [ABSTRACT FROM AUTHOR]

The colored neighborhood metric for sparse graphs was introduced by Bollobás and Riordan []. The corresponding convergence notion refines a convergence notion introduced by Benjamini and Schramm []. We prove that even in this refined sense, the limit of a convergent graph sequence (with uniformly bounded degree) can be represented by a graphing. We study various topics related to this convergence notion such as: Bernoulli graphings, factor of i.i.d. processes and hyperfiniteness. [ABSTRACT FROM AUTHOR]

Image-based rendering (IBR) creates realistic images by enriching simple geometries with photographs, e.g., mapping the photograph of a building façade onto a plane. However, as soon as the viewer moves away from the correct viewpoint, the image in the retina becomes distorted, sometimes leading to gross misperceptions of the original geometry. Two hypotheses from vision science state how viewers perceive such image distortions, one claiming that they can compensate for them (and therefore perceive scene geometry reasonably correctly), and one claiming that they cannot compensate (and therefore can perceive rather significant distortions). We modified the latter hypothesis so that it extends to street-level IBR. We then conducted a rigorous experiment that measured the magnitude of perceptual distortions that occur with IBR for façade viewing. We also conducted a rating experiment that assessed the acceptability of the distortions. The results of the two experiments were consistent with one another. They showed that viewers' percepts are indeed distorted, but not as severely as predicted by the modified vision science hypothesis. From our experimental results, we develop a predictive model of distortion for street-level IBR, which we use to provide guidelines for acceptability of virtual views and for capture camera density. We perform a confirmatory study to validate our predictions, and illustrate their use with an application that guides users in IBR navigation to stay in regions where virtual views yield acceptable perceptual distortions. [ABSTRACT FROM AUTHOR]

Background: When assessing the concordance between two methods of measurement of ordinal categorical data, summary measures such as Cohen's (1960) kappa or Bangdiwala's (1985) B-statistic are used. However, a picture conveys more information than a single summary measure. Methods: We describe how to construct and interpret Bangdiwala's (1985) agreement chart and illustrate its use in visually assessing concordance in several example clinical applications. Results: The agreement charts provide a visual impression that no summary statistic can convey, and summary statistics reduce the information to a single characteristic of the data. However, the visual impression is personal and subjective, and not usually reproducible from one reader to another. Conclusions: The agreement chart should be used to complement the summary kappa or B-statistics, not to replace them. The graphs can be very helpful to researchers as an early step to understand relationships in their data when assessing concordance. [ABSTRACT FROM AUTHOR]

ABSTRACT: Calculating the seismic displacement of reinforced retaining walls is important for optimal design of these structures. Using the limit analysis theorem, in this study an innovative approach has been proposed for calculating the coefficient of yield acceleration and permanent displacements of geosynthetic-reinforced soil-retaining walls with full-height rigid concrete facing (GRS-FHR walls). In this manner, based on the upper-bound theory of limit analysis and Newmark's sliding block theory, a group of charts has been proposed to estimate the permanent sliding displacements and the coefficient of yield acceleration for this type of wall. In these charts, the effect of the following parameters on the magnitude of permanent displacements and on the coefficient of yield acceleration of the wall has been investigated: vertical spacing of reinforcements; ratio of width to height of facing; ratio of length of reinforcements to height of facing; and internal friction angle of the soil. Results obtained from the suggested method have been compared with the sliding displacements reported by other researchers as well as those measured at the toe of a well-known GRS-FHR wall called Tanata under the Kobe earthquake (Japan, 1995). The suggested charts are believed to provide an appropriate, handy tool for estimating the coefficient of yield acceleration and permanent sliding displacements of GRS-FHR retaining walls. [ABSTRACT FROM AUTHOR]

Abstract: Let denote an -vertex and -edge graph in which is a function mapping each vertex to a positive weight and is a function mapping each edge to a positive length . Given a positive integer , the -Center problem involves finding a set with vertices of to be the locations for building facilities. The objective is to minimize the maximum weighted distance from each vertex in – to its nearest vertex in . This paper considers a practical restriction: the induced subgraph of the selected vertices must be connected. The new variant is called the Connected -Center problem (the problem). For each fixed integer , on block graphs with exactly blocks, we first show that the problem is NP-hard when (1) , for all vertices , and , for all edges , and (2) , for all vertices , and , for all edges , respectively. Second, an -time algorithm for solving the problem on block graphs with unit vertex-weights and unit edge-lengths is proposed. Then, the algorithmic result is extended to handle the situation in which some vertices in cannot be included to form feasible solutions. The complexity of the extended algorithm is also . [Copyright &y& Elsevier]

In an attempt to study the emerging questions about design of mathematical tasks that could support the solving of challenging problems, we designed two settings of interactive diagrams that share an example represented as an animation of multi-process motion but differ in their organizational functions. The interactive settings, each comprising of one task, were designed to support investigation in which the embedded animated example was expected to offer representative and general views. We analyzed the inquiry processes of 13- and 14-year-old interviewees and hypothesized whether these cases could represent more general considerations for the design of animated examples within a setting of interactive diagrams. We argue that (a) self-controlling the number of representations, (b) self-controlling the appearance of simultaneous information, (c) flexibly using links between dynamic and static representations, and (d) establishing links or completing partial links between representations are valuable inquiry processes in solving a problem that includes animated examples to enable viewing the representativeness of a given example. [ABSTRACT FROM AUTHOR]

A cardinal characteristic can often be described as the smallest size of a family of secardinalquences which has a given property. Instead of this traditional concern for a smallest realization of the given property, a basically new approach, taken in [4] and [5], asks for a realization whose members are sequences of labels that correspond to 1-way infinite paths in a labelled graph. We study this approach as such, establishing tools that are applicable to all these cardinal characteristics. As an application, we demonstrate the power of the tools developed by presenting a short proof of the bounded graph conjecture [4]. [ABSTRACT FROM AUTHOR]

The article presents a research paper that discusses aspects of amply regular locally GQ (5, 3)-graphs. It discusses the angulation of the graph in which the degree of vertex is defined as the number of vertices in its neighborhood and regarded as the amply regular graph with parameters. It notes that a point can be called collinear if they lie in a common block and they are called a set of straight lines L if any blocks intersect in at most one point. It also discusses several terminologies, computations and lemmas in the graph's formula.

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O( n2) “moves” between simple polygons. Each move is composed of a sequence of atomic moves called “stretches” and “twangs,” which walk between weakly simple “polygonal wraps” of S. These moves show promise to serve as a basis for generating random polygons. [ABSTRACT FROM AUTHOR]

Let G be a graph. A set S of vertices of G is called a total dominating set of G if every vertex of G is adjacent to at least one vertex in S: The total domination number γt(G) and the matching number α'(G) of G are the cardinalities of the minimum total dominating set and the maximum matching of G; respectively. In this paper, we introduce an upper bound of the difference between γt(G) and α'(G): We also characterize every tree T with γt(T) ⩽ α'(T); and give a family of graphs with γt(G) ⩽ α'(G). [ABSTRACT FROM AUTHOR]

The class of even-hole-free graphs is structurally quite similar to the class of perfect graphs, which was the key initial motivation for their study. The techniques developed in the study of even-hole-free graphs were generalized to other complex hereditary graph classes, and in the case of perfect graphs led to the famous resolution of the Strong Perfect Graph Conjecture and their polynomial time recognition. The class of even-hole-free graphs is also of independent interest due to its relationship to β-perfect graphs. In this survey we describe all the different structural characterizations of even-hole- free graphs, focusing on their algorithmic consequences. [ABSTRACT FROM AUTHOR]

In this paper we study proximity graph structures like Delaunay triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define Voronoi diagrams, Delaunay triangulations, relative neighborhood graphs, Gabriel graphs which are related to the graph structure and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks. [ABSTRACT FROM AUTHOR]

In this paper we present an approach for the analysis of graph transformation rules based on an intermediate OCL representation. We translate different rule semantics into OCL, together with the properties of interest (like rule applicability, conflicts or independence). The intermediate representation serves three purposes: (1) it allows the seamless integration of graph transformation rules with the MOF and OCL standards, and enables taking the meta-model and its OCL constraints (i.e. well-formedness rules) into account when verifying the correctness of the rules; (2) it permits the interoperability of graph transformation concepts with a number of standards-based model-driven development tools; and (3) it makes available a plethora of OCL tools to actually perform the rule analysis. This approach is especially useful to analyse the operational semantics of Domain Specific Visual Languages. We have automated these ideas by providing designers with tools for the graphical specification and analysis of graph transformation rules, including a back-annotation mechanism that presents the analysis results in terms of the original language notation. [ABSTRACT FROM AUTHOR]

If G is a graph, a G-decomposition of a host graph H is a partition of the edges of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition of H is the minimum number of colors required to color the parts of the decomposition so that parts which share a common node get different colors. We establish an upper bound on the chromatic index and characterize those decompositions which achieve it. The structurally most interesting of the decompositions with maximal chromatic index are associated with ( v, k, 1)-designs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. For $${x,y\in V(G)}$$ with d( x, y) = 2, we define $${J(x,y)= \{u \in N(x)\cap N(y)\mid N[u] \subseteq N[x] \,{\cup}\,N[y] \}}$$ and $${J'(x,y)= \{u \in N(x) \cap N(y)\,{\mid}\,{\rm if}\ v \in N(u){\setminus}(N[x] \,{\cup}\, N[y])\ {\rm then}\ N[x] \,{\cup}\, N[y]\,{\cup}\,N[u]{\setminus}\{x,y\}\subseteq N[v]\}}$$. A graph G is quasi-claw-free if $${J(x,y) \not= \emptyset}$$ for each pair ( x, y) of vertices at distance 2 in G. Broersma and Vumar (in Math Meth Oper Res. doi:) introduced $${\mathcal{P}_{3}}$$-dominated graphs defined as $${J(x,y)\,{\cup}\, J'(x,y)\not= \emptyset}$$ for each $${x,y \in V(G)}$$ with d( x, y) = 2. This class properly contains that of quasi-claw-free graphs, and hence that of claw-free graphs. In this note, we prove that a 2-connected $${\mathcal{P}_3}$$-dominated graph is 1-tough, with two exceptions: K2,3 and K1,1,3, and prove that every even connected $${\mathcal{P}_3}$$-dominated graph $${G\ncong K_{1,3}}$$ has a perfect matching. Moreover, we show that every even (2 p + 1)-connected $${\mathcal{P}_3}$$-dominated graph is p-extendable. This result follows from a stronger result concerning factor-criticality of $${\mathcal{P}_3}$$-dominated graphs. [ABSTRACT FROM AUTHOR]

A star-factor of a graph is a spanning subgraph each of whose components is a star. A graph G is called star-uniform if all star-factors of G have the same number of components. Motivated by the minimum cost spanning tree and the optimal assignment problems, Hartnell and Rall posed an open problem to characterize all the star-uniform graphs. In this paper, we show that a graph G is star-uniform if and only if G has equal domination and matching number. From this point of view, the star-uniform graphs were characterized by Randerath and Volkmann. Unfortunately, their characterization is incomplete. By deploying Gallai–Edmonds Matching Structure Theorem, we give a clear and complete characterization of star-unform graphs. [ABSTRACT FROM AUTHOR]

We show that if G is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of G needed to cover E( G) equals the chromatic number of the complement of the square of line graph of G. Using this, we establish that for a chordal bipartite graph G, the minimum number of chain subgraphs of G needed to cover E( G) equals the size of a largest induced matching in G, and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph. [ABSTRACT FROM AUTHOR]

The strong product $${G\boxtimes H}$$ of graphs G = ( V1, E1) and H = ( V2, E2) is the graph with vertex set $${V(G \boxtimes H)=V_1\times V_2}$$, where two distinct vertices $${(x_1, x_2), (y_1, y_2)\in V_1\times V_2}$$ are adjacent in $${G\boxtimes H}$$ if and only if x i = y i or $${x_i y_i\in E_i}$$ for i = 1, 2. We introduce so called I-sets and L-sets in the strong product $${G\boxtimes H}$$ and prove that every minimum separating set in $${G\boxtimes H}$$ is either an I-set or an L-set in $${G\boxtimes H}$$. Some bounds and exact results for connectivity of strong products follow from this characterization. The result is then generalized to an arbitrary number of factors in the strong product. [ABSTRACT FROM AUTHOR]

Let G = ( V, E) be a simple undirected graph. N( G) = ( V, E N) is the neighborhood graph of the graph G, if and only if We present several structural properties of N( G) and characterize the hamiltonicity of N( G) by means of chords of a hamiltonian cycle in G. [ABSTRACT FROM AUTHOR]

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least $${\frac{1}{2}|G|}$$ vertices of degree 5. [ABSTRACT FROM AUTHOR]

Three distinct points [image omitted] and [image omitted] with [image omitted] are taken, respectively on the x, y and the z-axes of a rectangular coordinate system in [image omitted] Using the converse of the theorem of Pythagoras, it is shown that the triangle [image omitted] can never be a right-angled triangle. The result seems to be intuitive, but nevertheless requires a proof. As an application, some intuitive results about a tetrahedron are confirmed. [ABSTRACT FROM AUTHOR]