905 resultados para the Cuban degree
Resumo:
The boxicity of a graph H, denoted by View the MathML source, is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in View the MathML source. In this paper we show that for a line graph G of a multigraph, View the MathML source, where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, View the MathML source. For the d-dimensional hypercube Qd, we prove that View the MathML source. The question of finding a nontrivial lower bound for View the MathML source was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).
Resumo:
An axis-parallel box in $b$-dimensional space is a Cartesian product $R_1 \times R_2 \times \cdots \times R_b$ where $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its boxicity is the minimum dimension $b$, such that $G$ is representable as the intersection graph of (axis-parallel) boxes in $b$-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an $O(\Delta n^2 \ln^2 n)$ randomized algorithm to construct a box representation for any graph $G$ on $n$ vertices in $\lceil (\Delta + 2)\ln n \rceil$ dimensions, where $\Delta$ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in $O(n^4 \Delta )$ time. Here, we present an $O(n^2 \Delta^2 \ln n)$ deterministic algorithm that constructs the box representation for any graph in $\lceil (\Delta + 2)\ln n \rceil$ dimensions.
Resumo:
Ballast fouling is created by the breakdown of aggregates or outside contamination by coal dust from coal trains, or from soil intrusion beneath rail track. Due to ballast fouling, the conditions of rail track can be deteriorated considerably depending on the type of fouling material and the degree of fouling. So far there is no comprehensive guideline available to identify the critical degree of fouling for different types of fouling materials. This paper presents the identification of degree of fouling and types of fouling using non-destructive testing, namely seismic surface-wave and ground penetrating radar (GPR) survey. To understand this, a model rail track with different degree of fouling has been constructed in Civil engineering laboratory, University of Wollongong, Australia. Shear wave velocity obtained from seismic survey has been employed to identify the degree of fouling and types of fouling material. It is found that shear wave velocity of fouled ballast increases initially, reaches optimum fouling point (OFP), and decreases when the fouling increases. The degree of fouling corresponding after which the shear wave velocity of fouled ballast will be smaller than that of clean ballast is called the critical fouling point (CFP). Ground penetrating radar with four different ground coupled antennas (500 MHz, 800 MHz, 1.6 GHz and 2.3 GHz) was also used to identify the ballast fouling condition. It is found that the 800 MHz ground coupled antenna gives a better signal in assessing the ballast fouling condition. Seismic survey is relatively slow when compared to GPR survey however it gives quantifiable results. In contrast, GPR survey is faster and better in estimating the depth of fouling. (C) 2011 Elsevier B.V. All rights reserved.
Resumo:
The boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R(k). In this paper we show that for a line graph G of a multigraph, box(G) <= 2 Delta (G)(inverted right perpendicularlog(2) log(2) Delta(G)inverted left perpendicular + 3) + 1, where Delta(G) denotes the maximum degree of G. Since G is a line graph, Delta(G) <= 2(chi (G) - 1), where chi (G) denotes the chromatic number of G, and therefore, box(G) = 0(chi (G) log(2) log(2) (chi (G))). For the d-dimensional hypercube Q(d), we prove that box(Q(d)) >= 1/2 (inverted right perpendicularlog(2) log(2) dinverted left perpendicular + 1). The question of finding a nontrivial lower bound for box(Q(d)) was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795-5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). (C) 2011 Elsevier B.V. All rights reserved.
Resumo:
We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.
Resumo:
The efficiency of track foundation material gradually decreases due to insufficient lateral confinement, ballast fouling, and loss of shear strength of the subsurface soil under cyclic loading. This paper presents characterization of rail track subsurface to identify ballast fouling and subsurface layers shear wave velocity using seismic survey. Seismic surface wave method of multi-channel analysis of surface wave (MASW) has been carried out in the model track and field track for finding out shear wave velocity of the clean and fouled ballast and track subsurface. The shear wave velocity (SWV) of fouled ballast increases with increase in fouling percentage, and reaches a maximum value and then decreases. This character is similar to typical compaction curve of soil, which is used to define optimum and critical fouling percentage (OFP and CFP). Critical fouling percentage of 15 % is noticed for Coal fouled ballast and 25 % is noticed for clayey sand fouled ballast. Coal fouled ballast reaches the OFP and CFP before clayey sand fouled ballast. Fouling of ballast reduces voids in ballast and there by decreases the drainage. Combined plot of permeability and SWV with percentage of fouling shows that after critical fouling point drainage condition of fouled ballast goes below acceptable limit. Shear wave velocities are measured in the selected location in the Wollongong field track by carrying out similar seismic survey. In-situ samples were collected and degrees of fouling were measured. Field SWV values are more than that of the model track SWV values for the same degree of fouling, which might be due to sleeper's confinement. This article also highlights the ballast gradation widely followed in different countries and presents the comparison of Indian ballast gradation with international gradation standards. Indian ballast contains a coarser particle size when compared to other countries. The upper limit of Indian gradation curve matches with lower limit of ballast gradation curves of America and Australia. The ballast gradation followed by Indian railways is poorly graded and more favorable for the drainage conditions. Indian ballast engineering needs extensive research to improve presents track conditions.
Resumo:
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011
Resumo:
This paper presents the results of seismic response analysis of layered ground in Ahmedabad City during the earthquake in Bhuj on 26(th) January 2001. An attempt has been made to understand the reasons for the failure of multistoreyed buildings founded on soft alluvial deposits in Ahmedabad. Standard Penetration test at a site very close to the Sabarmati river belt was carried out for geotechnical investigations. The program SHAKE91, widely used in the field of earthquake engineering for computing the seismic response of horizontally layered soil deposits, was used to analyse the soil profile at the selected site considering the ground as one dimensional layered elastic system. The ground accelerations recorded at the ground floor of the Regional Passport Staff Quarters building, which is very close to the investigated site, was used as input motion. Also, Finite Element Analysis was carried out for different configurations of multistorey building frames for evaluating their natural frequencies and is compared with the predominant frequency of the layered soil system. The results reveal that the varying degree of damage to multistorey buildings in the close proximity of Sabarmati river area was essentially due to the large amplification of the ground and the near resonance condition.
Resumo:
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G) ? ? + 2, where ? = ?(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|-1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a'(G) ? ? + 3. Triangle-free planar graphs satisfy Property A. We infer that a'(G) ? ? + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). (C) 2011 Wiley Periodicals, Inc. J Graph Theory
Resumo:
Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph GD] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.
Resumo:
A unit cube in (or a k-cube in short) is defined as the Cartesian product R (1) x R (2) x ... x R (k) where R (i) (for 1 a parts per thousand currency sign i a parts per thousand currency sign k) is a closed interval of the form a (i) , a (i) + 1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G is the minimum k such that G has a k-cube representation. From a geometric embedding point of view, a k-cube representation of G = (V, E) yields an embedding such that for any two vertices u and v, ||f(u) - f(v)||(a) a parts per thousand currency sign 1 if and only if . We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree Delta in O(Delta ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(Delta ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b a parts per thousand currency sign n and b is much smaller than n for many well-known graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree Delta and bandwidth b, the cubicity is O(min{b, Delta ln b}). The upper bound of b + 1 is used to derive upper bounds for the cubicity of circular-arc graphs, cocomparability graphs and AT-free graphs in terms of the maximum degree Delta.
Resumo:
A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration. model is O(davlogn).
Resumo:
This study investigates the application of support vector clustering (SVC) for the direct identification of coherent synchronous generators in large interconnected multi-machine power systems. The clustering is based on coherency measure, which indicates the degree of coherency between any pair of generators. The proposed SVC algorithm processes the coherency measure matrix that is formulated using the generator rotor measurements to cluster the coherent generators. The proposed approach is demonstrated on IEEE 10 generator 39-bus system and an equivalent 35 generators, 246-bus system of practical Indian southern grid. The effect of number of data samples and fault locations are also examined for determining the accuracy of the proposed approach. An extended comparison with other clustering techniques is also included, to show the effectiveness of the proposed approach in grouping the data into coherent groups of generators. This effectiveness of the coherent clusters obtained with the proposed approach is compared in terms of a set of clustering validity indicators and in terms of statistical assessment that is based on the coherency degree of a generator pair.
Resumo:
A series of resonant column tests have been performed in the torsional mode of vibration to assess the effect of saturation, starting from the near dry state to the fully saturated state, on the damping ratio of sands corresponding to the threshold strain level. Tests were carried out on three different gradations of sand for various combinations of relative density and effective confining pressure. For fine sands, a certain optimum degree of saturation exists at which the damping ratio minimizes; it is known that a decrease in Sr from a fully saturated state leads to a continuous increase in the matric suction. With an increase in the relative density, the optimum degree of saturation for fine sand increases marginally from 1.38 to 1.49%, but does not show any dependency on the effective confining pressure. In contrast, the minimum values of the damping ratio for medium and coarse sands are found to always correspond to the near dry state. The damping ratio decreases continuously with increases in relative density and effective confining pressure. The threshold strain level has been found to decrease continuously with increases in relative density and effective confining pressure. (C) 2013 American Society of Civil Engineers.
Resumo:
Transparent glasses in CaO-Bi2O3-B2O3 system were fabricated via the conventional melt-quenching technique. X-ray powder diffraction (XRD) and differential thermal analysis (DTA) carried out on the as-quenched samples confirmed their amorphous and glassy nature respectively. The surface crystallization behaviour of these glasses with and without ultrasonic surface treatment (UST) was monitored using XRD, optical microscopy and scanning electron microscopy (SEM). The volume fraction, depth of crystallization and the (001) orientation factor for the heat treated samples with and without UST were compared. The ultrasonically-treated samples on subsequent heat treatment were found to crystallize at lower temperatures associated with the highest degree of orientation factor (0.95) in contrast with those of non-UST samples. These surface crystallized glasses were found to exhibit nonlinear optical behaviour emitting green light (532 nm) when they were exposed to the infrared radiation (1064 nm) using Nd:YAG laser.