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.
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.
18457324
On the higher-order edge toughness of a graph
For an integer c, 1?c??V(G)??1, we define the cth-order edge toughness of a graph G as tc(G)=min|X|?(G?X)?cX?E(G) & ?(G?X)>c The objective of this paper is to study this generalized concept of edge toughness. Besides giving the of the cth-order edge toughness ?c(G) of a graph G, we prove that `?c(G)?k if and only if G has k edge-disjoint spanning forests with exactly c components?. We also study the `balancity? of a graph G of order p and size q, which is defined as the smallest positive integer c such that ?c(G) = p/(p?c).
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).
448895
Search on the Semantic Web
To help human users and software agents find relevant knowledge on the Semantic Web, the Swoogle search engine discovers, indexes, and analyzes the ontologies and facts that are encoded in Semantic Web documents.
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.
15167056
Swoogle: Searching for Knowledge on the Semantic Web
Swoogle is an implemented system that discovers, analyzes and indexes knowledge encoded in semantic web documents on the Web. Swoogle reasons about these documents and their constituent parts (e.g., terms and triples) and records meaningful metadata about them. Swoogle provides webscale semantic web data access service, which helps human users and software systems to find relevant documents, terms and triples, via its search and navigation services. Swoogle also provides a customizable algorithm inspired by Google's PageRank algorithm but adapted to the semantics and use patterns found in semantic web documents.
18522080
Example of supersonic solutions to a steady state Euler-Poisson system
Abstract We give an example of supersonic solutions to a one-dimensional steady state Euler–Poisson system arising in the modeling of plasmas and semiconductors. The existence of the supersonic solutions which correspond to large current density is proved by Schauder’s fixed point theorem. We show also the uniqueness of solutions in the supersonic region.
183316
Modifying Bayesian Networks by Probability Constraints
This paper deals with the following problem: modify a Bayesian network to satisfy a given set of probability constraints by only change its conditional probability tables, and the probability distribution of the resulting network should be as close as possible to that of the original network. We propose to solve this problem by extending IPFP (iterative proportional fitting procedure) to probability distributions represented by Bayesian networks. The resulting algorithm E-IPFP is further developed to D-IPFP, which reduces the computational cost by decomposing a global E-IPFP into a set of smaller local E-IPFP problems. Limited analysis is provided, including the convergence proofs of the two algorithms. Computer experiments were conducted to validate the algorithms. The results are consistent with the theoretical analysis.