Thesis (Ph. D.)--Lehigh University, 2002. / Includes vita. Includes bibliographical references (leaves 60-61).

Convexity in graphs has been widely discussed in graph theory and G. Chartrand et al. introduced the convexity number of oriented graphs in 2002. In this thesis, we follow the notions addressed by them and develop an extension in some related topics of convexity in directed graphs. Let D be a connected oriented graph. A set S subseteq V(D) is convex in D if, for every pair of vertices x, yin S, the vertex set of every x-y geodesic (x-y shortest directed path) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. We show that for every possible triple n, m, k of integers except for k=4, there exists a strongly connected digraph D of order n, size m, and con(D)=k. Let G be a graph. We define the convexity spectrum S_{C}(G)={con(D): D is an orientation of G} and the strong convexity spectrum S_{SC}(G)={con(D): D is a strongly connected orientation of G}. Then S_{SC}(G) ⊆ S_{C}(G). We show that for any n ¡Ú 4, 1 ≤ a ≤ n-2 and a n ¡Ú 2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_{SC}(G)={a,n-1}, and there is no connected graph G of order n ≥ 3 with S_{SC}(G)={n-1}. We also characterizes the convexity spectrum and the strong convexity spectrum of complete graphs, complete bipartite graphs, and wheel graphs. Those convexity spectra are of different kinds. Let the difference of convexity spectra D_{CS}(G)=S_{C}(G)- S_{SC}(G) and the difference number of convexity spectra dcs(G) be the cardinality of D_{CS}(G) for a graph G. We show that 0 ≤ dcs(G) ≤ ⌊|V(G)|/2⌋, dcs(K_{r,s})=⌊(r+s)/2⌋-2 for 4 ≤ r ≤ s, and dcs(W_{1,n-1})= 0 for n ≥ 5. The convexity spectrum ratio of a sequence of simple graphs G_n of order n is r_C(G_n)= liminflimits_{n to infty} frac{|S_{C}(G_n)|}{n-1}. We show that for every even integer t, there exists a sequence of graphs G_n such that r_C(G_n)=1/t and a formula for r_C(G) in subdivisions of G.

No description available.

No description available.

Given a connected oriented graph D, we say that a subset S of V(D) is convex in D if, for every pair of vertices x, y in S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity number con (D) of a nontrivial connected oriented graph D is the maximum cardinality of a proper convex set of D. Let S_{C}(K_{n})={con(D)|D is an orientation of K_{n}} and S_{SC}(K_{n})={con(D)|D is a strong orientation of K_{n}}. We show that S_{C}(K_{3})={1,2} and S_{C}(K_{n})={1,3,4,...,n-1} if n >= 4. We also have that S_{SC}(K_{3})={1} and S_{SC}(K_{n})={1,3,4,...,n-2} if n >= 4 . We also show that every triple n, m, k of integers with n >= 5, 3 <= k <= n-2, and n+1 <= m <= n(n-1)/2, there exists a strong connected oriented graph D of order n with |E(D)|=m and con (D)=k.

This thesis investigates, develops and implements algorithms for shape- preserving curve and surface design that aim to reflect the shape characteristics of the underlying geometry by achieving a visually pleasing interpolant to a set of data points in one or two dimensions. All considered algorithms are local and useful in computer graphics applications. The thesis begins with an introduction to existing methods which attempt to solve the shape-preserving 1 curve interpolation problem using C cubic and quadratic splines. Next, a new generalized slope estimation method involving a parameter t, which is used to control the size of the estimated slope and, in turn, produces a more visually pleasing shape of the resulting curve, is proposed. Based on this slope generation formula, new automatic and interactive algorithms for constructing 1 shape-preserving curves from C quadratic and cubic splines are developed and demonstrated on a number of data sets. The results of these numerical experiments are also presented. Finally, a method suggested by Roulier which 1 generates C surfaces interpolating arbitrary sets of convex data on rectangular grids is considered in detail and modified to achieve more visually pleasing surfaces. Some numerical examples are given to demonstrate the performance of the method.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P&#8727; 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P&#8727; 3 in graphs with few P4âs. / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P&#8727; 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P&#8727; 3 in graphs with few P4âs.

This work is devoted to the theoretical and numerical aspects of shape optimization. The first part (chapter I to IV) deals with optimization problems under convexity constraint or constant width constraint. We give several new results related to Newton's problem and Meissner's conjecture. The second part (chapter V to VII) deals with the numerical study of shape optimization problems where many shapes or phases are involved. Some new numerical methods are introduced to study optimal configurations of famous problems : Kelvin's problem and Caffarelli's conjecture. The last part (chapter VIII and IX) is devoted to optimal transportation problems and irrigation problems. More precisely, we introduce a general framework, where different kind of cost functions are allowed. This seems relevant in some problems presenting congestion effects as for instance traffic on a highway, crowds moving in domains with obstacles. In the last chapter we give preliminary results related to the numerical approximation of optimal irrigation networks.

This thesis is an extension of a recent study into the relationship between merger size and profitability. It studies a class of Cournot oligopoly with linear cost and quadratic demand. Its focus is to analyze how a mergers profitability is affected by its size and by the demand elasticity. Such results have not yet been reported in previous studies, perhaps due to the complexity of the equilibrium equation involved. It shows an increase in the demand elasticity also raises a mergers profitability. Consequently, an increase in the demand elasticity reduces merged members critical combined per-merger market share for the merger to be profit enhancing. Comparing with 80% minimum market share requirement for a profitable merger in Salant, Switzer, and Reynolds (1983), a greater market share is needed when the demand function is concave (demand is relatively inelastic), while a smaller market share may still be profitable when the demand function is convex (demand is relatively elastic). In our model, mergers are generally detrimental to public interests by increasing market price and reducing output. However, the merger will be less harmful when the goods are very inelastic.

This thesis is an extension of a recent study into the relationship between merger size and profitability. It studies a class of Cournot oligopoly with linear cost and quadratic demand. Its focus is to analyze how a mergers profitability is affected by its size and by the demand elasticity. Such results have not yet been reported in previous studies, perhaps due to the complexity of the equilibrium equation involved. It shows an increase in the demand elasticity also raises a mergers profitability. Consequently, an increase in the demand elasticity reduces merged members critical combined per-merger market share for the merger to be profit enhancing. Comparing with 80% minimum market share requirement for a profitable merger in Salant, Switzer, and Reynolds (1983), a greater market share is needed when the demand function is concave (demand is relatively inelastic), while a smaller market share may still be profitable when the demand function is convex (demand is relatively elastic). In our model, mergers are generally detrimental to public interests by increasing market price and reducing output. However, the merger will be less harmful when the goods are very inelastic.