20234262
Chromatic equivalence classes of certain generalized polygon trees
Let P(G) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent, written G ~ H, if P(G) = P(H). Let ¢ denote the family of all generalized polygon trees with three interior regions. Xu (1994) showed that ¢ is a union of chromatic equivalence classes under the equivalence relation ',-/. In this paper, we determine infinitely many chromatic equivalence classes in ~ under ',-~'. As a byproduct, we obtain a family of chromatically unique graphs established by Peng (1995).
11039476
On the chromatic uniqueness of certain bipartite graphs
Let K(p, q), p ⩽ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. We denote by K-r(p, q), the family of all graphs obtained by deleting any r distinct edges from K(p, q). Teo and Koh showed that K-1(p, q) is chromatically unique (in short χ-unique) for all p, q such that 3 ⩽ p ⩽ q. In this paper, we obtain a sufficient condition for a graph in K-2(p, q) to be χ-unique. Using this result, we then prove that each graph in K-2(p, p + d) is χ-unique for p ⩾ 4and 0 ⩽ d ⩽ 3. For d ⩾ 4, the graphs in K-2(p, q + d) are χ-unique if p > (A + √B)/4d2, where A and B are polynomials in d. We also show that each graph (≇K(4, 4) – K(1, 3)) in K-3(p, p + d) is χ-unique, for p ⩾ 4 and d=0, 1; and all graphs in K-3(p, p + 2) are χ-unique if and only if all graphs in K-4(p + 1, p + 1) are χ-unique, where p ⩾ 4. Finally we prove that every graph in K-4(p, p + 1) is χ-unique for p ⩾ 5.
2551506
Chromatic Equivalence Classes of Certain Generalized Polygon Trees, II
Let P(G) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent, if P(G)=P(H). A set of graphs S is called a chromatic equivalence class if for any graph H that is chromatically equivalent with a graph G in S, then [email protected]?S. Peng et al. (Discrete Math. 172 (1997) 103-114), studied the chromatic equivalence classes of certain generalized polygon trees. In this paper, we continue that study and present a solution to Problem 2 in Koh and Teo (Discrete Math. 172 (1997) 59-78).
6604689
Chromaticity of certain tripartite graphs identified with a path
For a graph G, let P(G) be its chromatic polynomial. Two graphs G and H are chromatically equivalent if P(G)=P(H). A graph G is chromatically unique if P(H)=P(G) implies that [email protected]?G. In this paper, we classify the chromatic classes of graphs obtained from K"2","2","[email protected]?P"m(m>=3), (K"2","2","2-e)@?P"m(m>=5) and (K"2","2","2-2e)@?P"m(m>=6) by identifying the end-vertices of the path P"m with any two vertices of K"2","2","2, K"2","2","2-e and K"2","2","2-2e, respectively, where e and 2e are, respectively, an edge and any two edges of K"2","2","2. As a by-product of this, we obtain some families of chromatically unique and chromatically equivalent classes of graphs.
33972996
Chromatic equivalence classes of certain cycles with edges
Abstract Let P(G) denote the chromatic polynomial of a graph G . Two graphs G and H are chromatically equivalent, written G∼H , if P(G)=P(H) . A graph G is chromatically unique if for any graph H , G∼H implies that G is isomorphic with H . In this paper, we give the necessary and sufficient conditions for a family of generalized polygon trees to be chromatically unique.
42745
The chromaticity of s-bridge graphs and related graphs
Abstract The graph consisting of s paths joining two vertices is called s -bridge graph. In this paper, we discuss the chromaticity of some families of s -bridge graphs, especially 4-bridge graphs, and some graphs related to s -bridge graphs.
21181741
An alternative estimation method for the accelerated failure time frailty model
Frailty models based on the proportional hazards model are useful to analyze correlated or clustered failure time data. However, there has been some recent interest in a frailty model based on the popular accelerated failure time model for correlated failure time data ([Pan, W., 2001. Using frailties in the accelerated failure time model. Lifetime Data Anal. 7(1), 55-64], for example). In this paper we review recent advances on this model in the literature. We propose a general estimation method based on M-estimators and the EM algorithm to estimate the parameters in the model. To evaluate the performance of the proposed method, we carry out a simulation study. The results of the simulation study show that the proposed method performs well in comparison with existing estimation methods. As an illustration, the model and the proposed method are applied to analyze the effects of sublingual nitroglycerin and oral isosorbide dinitrate on angina pectoris of coronary heart disease patients [Danahy, D.T., Burwell, D.T., Aronow, W.S., Prakash, R., 1977. Sustained hemodynamic and antianginal effect of high dose oral isosorbide dinitrate. Circulation 55, 381-387].
17089555
Counting Small Cliques in 3-uniform Hypergraphs
Many applications of Szemeredi's Regularity Lemma for graphs are based on the following counting result. If ${\mathcal G}$ is an $s$-partite graph with partition $V({\mathcal G}) =\bigcup_{i=1}^{s} V_i$, $\vert V_i\vert =m$ for all $i\in [s]$, and all pairs $(V_i, V_j)$, $1\leq i < j\leq s$, are $\epsilon$-regular of density $d$, then $\mathcal{G}$ contains $(1\pm f(\epsilon))d^{({s\atop 2})}m^s$ cliques $K_{s}$, provided $\epsilon<\epsilon(d)$, where $f(\epsilon)$ tends to 0 as $\epsilon$ tends to 0.Guided by the regularity lemma for 3-uniform hypergraphs established earlier by Frankl and Rodl, Nagle and Rodl proved a corresponding counting lemma. Their proof is rather technical, mostly due to the fact that the ‘quasi-random’ hypergraph arising after application of Frankl and Rodl's regularity lemma is ‘sparse’, and consequently difficult to handle.When the ‘quasi-random’ hypergraph is ‘dense’ Kohayakawa, Rodl and Skokan (J. Combin. Theory Ser. A 97 307–352) found a simpler proof of the counting lemma. Their result applies even to $k$-uniform hypergraphs for arbitrary $k$. While the Frankl–Rodl regularity lemma will not render the dense case, in this paper, for $k=3$, we are nevertheless able to reduce the harder, sparse case to the dense case.Namely, we prove that a ‘dense substructure’ randomly chosen from the ‘sparse $\delta$-regular structure’ is $\delta$-regular as well. This allows us to count the number of cliques (and other subhypergraphs) using the Kohayakawa–Rodl–Skokan result, and provides an alternative proof of the counting lemma in the sparse case. Since the counting lemma in the dense case applies to $k$-uniform hypergraphs for arbitrary $k$, there is a possibility that the approach of this paper can be adopted to the general case as well.
16963632
Agents Making Sense of the Semantic Web
Effective use of the vast quantity of available information and services on the Internet will require multi-agent systems to be tightly integrated with existing web infrastructure. This however will be impossible unless the information on the web is presented in a semantic language, such as the DARPA Agent Markup Language (DAML), which is one aim of the “Semantic Web”. As part of our exploration of Semantic Web technology, and DAML in particular, we have constructed ITTALKS, a web-based system for automatic and intelligent notification of information technology talks. In this paper, we describe the ITTALKS system, and discuss the numerous ways in which the use of Semantic Web concepts and DAML extend its ability to provide an intelligent online service to both the human community and, more interestingly, the agents assisting them.
207155768
Swoogle: a search and metadata engine for the semantic web
Swoogle is a crawler-based indexing and retrieval system for the Semantic Web. It extracts metadata for each discovered document, and computes relations between documents. Discovered documents are also indexed by an information retrieval system which can use either character N-Gram or URIrefs as keywords to find relevant documents and to compute the similarity among a set of documents. One of the interesting properties we compute is <i>ontology rank</i>, a measure of the importance of a Semantic Web document.
5372255
Holes in Graphs
The celebrated Regularity Lemma of Szemeredi asserts that every sufficiently large graph $G$ can be partitioned in such a way that most pairs of the partition sets span $\epsilon$-regular subgraphs. In applications, however, the graph $G$ has to be dense and the partition sets are typically very small. If only one $\epsilon$-regular pair is needed, a much bigger one can be found, even if the original graph is sparse. In this paper we show that every graph with density $d$ contains a large, relatively dense $\epsilon$-regular pair. We mainly focus on a related concept of an $(\epsilon,\sigma)$-dense pair, for which our bound is, up to a constant, best possible.