Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Studies on some generalizations of line graph and the power domination problem in graphs

Department of Mathematics, Cochin University of Science and Technology

Median computation in graphs using consensus strategies

Following the Majority Strategy in graphs, other consensus strategies, namely Plurality Strategy, Hill Climbing and Steepest Ascent Hill Climbing strategies on graphs are discussed as methods for the computation of median sets of pro¯les. A review of algorithms for median computation on median graphs is discussed and their time complexities are compared. Implementation of the consensus strategies on median computation in arbitrary graphs is discussed

Convexity in multidimensional mechanism design

The present article initiates a systematic study of the behavior of a strictly increasing, C2 , utility function u(a), seen as a function of agents' types, a, when the set of types, A, is a compact, convex subset of iRm . When A is a m-dimensional rectangle it shows that there is a diffeomorphism of A such that the function U = u o H is strictly increasing, C2 , and strictly convexo Moreover, when A is a strictly convex leveI set of a nowhere singular function, there exists a change of coordinates H such that B = H-1(A) is a strictly convex set and U = u o H : B ~ iR is a strictly convex function, as long as a characteristic number of u is smaller than a characteristic number of A. Therefore, a utility function can be assumed convex in agents' types without loss of generality in a wide variety of economic environments.

Tendências econômicas e sociais na América Latina e no Caribe em gráficos = Economic and social trends in Latin America and the Caribbean in graphs = Tendencias económicas y sociales en América Latina y el Caribe en gráficos

Incluye Bibliografía

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

Students’ understanding of the function-derivative relationship when learning economic concepts

The aim of this study is to characterise students’ understanding of the function-derivative relationship when learning economic concepts. To this end, we use a fuzzy metric (Chang 1968) to identify the development of economic concept understanding that is defined by the function-derivative relationship. The results indicate that the understanding of these economic concepts is linked to students’ capacity to perform conversions and treatments between the algebraic and graphic registers of the function-derivative relationship when extracting the economic meaning of concavity/convexity in graphs of functions using the second derivative.

Some Problems In Algebra And Topology A Study Of Fuzzy Convexity With Special Reference To Separation Properties

This thesis is a study of abstract fuzzy convexity spaces and fuzzy topology fuzzy convexity spaces No attempt seems to have been made to develop a fuzzy convexity theoryin abstract situations. The purpose of this thesis is to introduce fuzzy convexity theory in abstract situations

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Method for Estimating the Magnitude and Frequency of Floods at Ungaged Sites on Unregulated Rural Streams in Iowa, HR-268, 1987

This report provides techniques and procedures for estimating the probable magnitude and frequency of floods at ungaged sites on Iowa streams. Physiographic characteristics were used to define the boundaries of five hydrologic regions. Regional regression equations that relate the size of the drainage area to flood magnitude are defined for estimating peak discharges having specified recurrence intervals of 2, 5, 10, 25, 50, and 100 years. Regional regression equations are applicable to sites on streams that have drainage areas ranging from 0.04 to 5,150 square miles provided that the streams are not affected significantly by regulation upstream from the sites and that the drainage areas upstream from the sites are not mostly urban areas. Flood-frequency characteristics for the mainstems of selected rivers are presented in graphs as a function of drainage area.

UNIVERSALITY OF RANDOM GRAPHS

We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.