Consensus strategies for signed profiles on graphs

The median problem is a classical problem in Location Theory: one searches for a location that minimizes the average distance to the sites of the clients. This is for desired facilities as a distribution center for a set of warehouses. More recently, for obnoxious facilities, the antimedian was studied. Here one maximizes the average distance to the clients. In this paper the mixed case is studied. Clients are represented by a profile, which is a sequence of vertices with repetitions allowed. In a signed profile each element is provided with a sign from f+; g. Thus one can take into account whether the client prefers the facility (with a + sign) or rejects it (with a sign). The graphs for which all median sets, or all antimedian sets, are connected are characterized. Various consensus strategies for signed profiles are studied, amongst which Majority, Plurality and Scarcity. Hypercubes are the only graphs on which Majority produces the median set for all signed profiles. Finally, the antimedian sets are found by the Scarcity Strategy on e.g. Hamming graphs, Johnson graphs and halfcubes

Median graphs, the remoteness function, periphery transversals, and geodetic number two

A periphery transversal of a median graph G is introduced as a set of vertices that meets all the peripheral subgraphs of G. Using this concept, median graphs with geodetic number 2 are characterized in two ways. They are precisely the median graphs that contain a periphery transversal of order 2 as well as the median graphs for which there exists a profile such that the remoteness function is constant on G. Moreover, an algorithm is presented that decides in O(mlog n) time whether a given graph G with n vertices and m edges is a median graph with geodetic number 2. Several additional structural properties of the remoteness function on hypercubes and median graphs are obtained and some problems listed

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.

The P3 Intersection Graph

We define a new graph operator called the P3 intersection graph, P3(G)- the intersection graph of all induced 3-paths in G. A characterization of graphs G for which P-3 (G) is bipartite is given . Forbidden subgraph characterization for P3 (G) having properties of being chordal , H-free, complete are also obtained . For integers a and b with a > 1 and b > a - 1, it is shown that there exists a graph G such that X(G) = a, X(P3( G)) = b, where X is the chromatic number of G. For the domination number -y(G), we construct graphs G such that -y(G) = a and -y (P3(G)) = b for any two positive numbers a > 1 and b. Similar construction for the independence number and radius, diameter relations are also discussed.

ON THE MEDIAN AND THE ANTIMEDIAN OF A COGRAPH

this paper, the median and the antimedian of cographs are discussed. It is shown that if G, and G2 are any two cographs, then there is a cograph that is both Eulerian and Hamiltonian having Gl as its median and G2 as its antimedian. Moreover, the connected planar and outer planar cographs are characterized and the median and antimedian graphs of connected, planar cographs are listed.

Studies on Some Graph Classes

Department of Mathematics, Cochin University of Science and Technology

Bioactivity Profile of Polyunsaturated Fattyacid extracts from Sardinella longiceps and Sardinella fimbriata – A comparative study

The oceans have proved to be an interminable source of new and effective drugs. Innumerable studies have proved that specific compounds isolated from marine organisms have great nutritional and pharmaceutical value. Polyunsaturated fattyacids (PUFA) in general are known for their dietary benefits in preventing and curing several critical ailments including Coronary heart disease (CHD) and cancers of various kinds. Eicosapentaenoic Acid (EPA) and Docosahexaenoic Acid (DHA) are two PUFA which are entirely marine in origin – and small Clupeoid fishes like sardines are known to be excellent sources of these two compounds. In this study, we selected two widely available Sardine species in the west coast, Sardinella longiceps and Sardinella fimbriata, for a comparative analysis of their bioactive properties. Both these sardines are known to be rich in EPA and DHA, however considerable seasonal variation in its PUFA content was expected and these variations studied. An extraction procedure to isolate PUFA at high purity levels was identified and the extracts obtained thus were studied for anti-bacterial, anti-diabetic and anti-cancerous properties.Samples of both the sardines were collected from landing centre, measured and their gut content analysed in four different months of the year – viz. June, September, December and March. The fish samples were analyzed for fattyacid using FAME method using gas chromatography to identify the full range of fattyacids and their respective concentration in each of the samples. The fattyacids were expressed in mg/g meat and later converted to percentage values against total fatty acids and total PUFA content. Fattyacids during winter season (Dec-Mar) were found to be generally higher than spawning season (June-Sept). PUFA dominated the profiles of both species and average PUFA content was also higher during winter. However, it was found that S. longiceps had proportionately higher EPA as compared to S. fimbriata which was DHA rich. Percentage of EPA and DHA also varied across months for both species – the spawning season seemed to show higher EPA content in S. longiceps and higher DHA content in S. fimbriata. Gut content analysis indicate that adult S. fimbriata is partial to zooplanktons which are DHA rich while adult S. longiceps feed mainly on EPA rich phytoplankton. Juveniles of both species, found mainly in winter, had a gut content showing more mixed diet. This difference in the feeding pattern reflect clearly in their PUFA profile – adult S. longiceps, which dominate the catch during the spawn season, feeding mostly on phytoplankton is concentrated with EPA while the juveniles which are found mostly in the winter season has slightly less EPA proportion as compared to adults. The same is true for S. fimbriata adults that are caught mostly in the spawning season; being rich in DHA as they feed mainly on zooplankton while the juveniles caught during winter season has a relatively lower concentration of DHA in their total PUFA.Various extraction procedures are known to obtain PUFA from fish oil. However, most of them do not give high purity and do not use materials indicated as safe. PUFA extracts have to be edible and should not have harmful substances for applying on mice and human subjects. Some PUFA extraction procedures, though pure and non-toxic, might induce cis-trans conversions during the extraction process. This conversion destroys the benefits of PUFA and at times is harmful to human body. A method free from these limitations has been standardized for this study. Gas Chromatography was performed on the extracts thus made to ensure that it is substantially pure. EPA: DHA ratios for both samples were derived - for S. longiceps this ratio was 3:2, while it was 3:8 for S. fimbriata.Eight common strains of gram positive and gram negative bacterial strains were subjected to the PUFA extracts from both species dissolved in acetone solution using Agar Well Diffusion method. The activity was studied against an acetone control. At the end of incubation period, zones of inhibition were measured to estimate the activity. Minimum inhibitory concentration for each of the active combinations was calculated by keeping p < 0.01 as significant. Four of the bacteria including multi-resistant Staphylococcus aureus were shown to be inhibited by the fish extracts. It was also found that the extracts from S. fimbriata were better than the one from S. longiceps in annihilating harmful bacteria.Four groups of mice subjects were studied to evaluate the antidiabetic properties of the PUFA extracts. Three groups were induced diabetes by administration of alloxan tetra hydrate. One group without diabetes was kept as control and another with diabetes was kept as diabetic control. For two diabetic groups, a prescribed amount of fish extracts were fed from each of the extracts. The biochemical parameters like serum glucose, total cholesterol, LDL & HDL cholesterol, triglycerides, urea and creatinine were sampled from all four groups at regular intervals of 7 days for a period of 28 days. It was found that groups fed with fish extracts had marked improvement in the levels of total LDL & HDL cholesterol, triglycerides and creatinine. Groups fed with extracts from S. fimbriata seem to have fared better as compared to S. longiceps. However, both groups did not show any marked improvement in blood glucose levels or levels of urea.Cell lines of MCF-7 (Breast Cancer) and DU-145 (Prostate Cancer) were used to analyse the cytotoxicity of the PUFA extracts. Both cell lines were subjected to MTT Assay and later the plates were read using an ELISA reader at a wavelength of 570nm. It was found that both extracts had significant cytotoxic effects against both cell lines and a peak cytotoxicity of 85-90% was apparent. IC50 values were calculated from the graphs and it was found that S. longiceps extracts had a slightly lower IC50 value indicating that it is toxic even at a lower concentration as compared to extracts from S. fimbriata.This study summarizes the bioactivity profile of PUFA extracts and provides recommendation for dietary intake; fish based nutritional industry and indigenous pharmaceutical industry. Possible future directions of this study are also elaborated.

Convex extendable trees

The concept of convex extendability is introduced to answer the problem of finding the smallest distance convex simple graph containing a given tree. A problem of similar type with respect to minimal path convexity is also discussed.

Axiomatic Characterization of the Antimedian Function on Paths and Hypercubes

An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a vertex maximizing the sum of the distances to the elements of the pro le. The antimedian function is de ned on the set of all pro les on G and has as output the set of antimedians of a pro le. It is a typical location function for nding a location for an obnoxious facility. The `converse' of the antimedian function is the median function, where the distance sum is minimized. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper such a characterization is obtained for the two classes of graphs on which the antimedian is well-behaved: paths and hypercubes.

Median Sets and Median Number of a Graph

A profile is a finite sequence of vertices of a graph. The set of all vertices of the graph which minimises the sum of the distances to the vertices of the profile is the median of the profile. Any subset of the vertex set such that it is the median of some profile is called a median set. The number of median sets of a graph is defined to be the median number of the graph. In this paper, we identify the median sets of various classes of graphs such as Kp − e, Kp,q forP > 2, and wheel graph and so forth. The median numbers of these graphs and hypercubes are found out, and an upper bound for the median number of even cycles is established.We also express the median number of a product graph in terms of the median number of their factors.

On the generalized obnoxious center problem: antimedian subsets

The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered.

On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes