In this paper,we obtain the thickness for some complete k-partite graphs for k=2,3.We first compute the thickness of K_(n,n+8)by giving a planar decomposition of K_(4k-1,4k+7)for k≥3.Then,two planar decompositions fo...In this paper,we obtain the thickness for some complete k-partite graphs for k=2,3.We first compute the thickness of K_(n,n+8)by giving a planar decomposition of K_(4k-1,4k+7)for k≥3.Then,two planar decompositions for K_(1,g,g)(g-1)when g is even and for K^(1,g,1/2(g-1)2)when g is odd are obtained.Using a recursive construction,we also obtain the thickness for some complete tripartite graphs.The results here support the long-standing conjecture that the thickness of K_(m,n)is[mn/2(m+n-2)]for any positive integers m,n.展开更多
Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guarantee...Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.展开更多
An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and...An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and indegree respectively of x. Define aui： dui^＋ - dus^-, bvj = dvj^＋ - dvj^- and cwk = dwk^＋ - dwk^- as the imbalances of the vertices ui in U, vj in V and wk in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite graph. Keywords Digraph, imbalance, outdegree, indegree, oriented graph, oriented tripartite graph, arc展开更多
Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A com...Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.展开更多
Preference prediction is the building block of personalized services,and its implementation at the group level helps enterprises identify their target customers effectively.Existing methods for preference prediction m...Preference prediction is the building block of personalized services,and its implementation at the group level helps enterprises identify their target customers effectively.Existing methods for preference prediction mainly focus on behavioral interactions to extract the associations between groups and products,ignoring the importance of other auxiliary records(e.g.,online reviews and social tags)in association detection.This paper proposes a novel method named GMAT for group preference prediction,aiming to collectively detect the sophisticated association patterns from user generated content(UGC)and behavioral interactions.In doing so,we construct a tripartite graph to collaborate these two types of data,and design a deep-learning algorithm with mutual attention module for generating the contextualized representations of groups and products.Extensive experiments on two real-world datasets show that GMAT is superior to other baselines in terms of group preference prediction.Additionally,GMAT is able to improve prediction accuracy compared with its different variants,further verifying the proposed method’s effectiveness on association pattern detection.展开更多
In the densification of Device-to-Device(D2D)-enabled Social Internet of Things(SIoT)networks,improper allocation of resources can lead to high interference,increased signaling overhead,latency,and disruption of Chann...In the densification of Device-to-Device(D2D)-enabled Social Internet of Things(SIoT)networks,improper allocation of resources can lead to high interference,increased signaling overhead,latency,and disruption of Channel State Information(CSI).In this paper,we formulate the problem of sum throughput maximization as a Mixed Integer Non-Linear Programming(MINLP)problem.The problem is solved in two stages:a tripartite graph-based resource allocation stage and a time-scale optimization stage.The proposed approach prioritizes maintaining Quality of Service(QoS)and resource allocation to minimize power consumption while maximizing sum throughput.Simulated results demonstrate the superiority of the proposed algorithm over standard benchmark schemes.Validation of the proposed algorithm using performance parameters such as sum throughput shows improvements ranging from 17%to 93%.Additionally,the average time to deliver resources to CSI users is minimized by 60.83%through optimal power usage.This approach ensures QoS requirements are met,reduces system signaling overhead,and significantly increases D2D sum throughput compared to the state-of-the-art schemes.The proposed methodology may be well-suited to address the challenges SIoT applications,such as home automation and higher education systems.展开更多
Most entity ranking research aims to retrieve a ranked list of entities from a Web corpus given a user query. The rank order of entities is determined by the relevance between the query and contexts of entities. Howev...Most entity ranking research aims to retrieve a ranked list of entities from a Web corpus given a user query. The rank order of entities is determined by the relevance between the query and contexts of entities. However, entities can be ranked directly based on their relative importance in a document collection, independent of any queries. In this paper, we introduce an entity ranking algorithm named NERank＋. Given a document collection, NERank＋ first constructs a graph model called Topical Tripartite Graph, consisting of document, topic and entity nodes. We design separate ranking functions to compute the prior ranks of entities and topics, respectively. A meta-path constrained random walk algorithm is proposed to propagate prior entity and topic ranks based on the graph model. We evaluate NERank＋ over real-life datasets and compare it with baselines. Experimental results illustrate the effectiveness of our approach.展开更多
基金supported by the JSSCRC(Grant No.2021530)NNSFC under Grant No.12271392。
文摘In this paper,we obtain the thickness for some complete k-partite graphs for k=2,3.We first compute the thickness of K_(n,n+8)by giving a planar decomposition of K_(4k-1,4k+7)for k≥3.Then,two planar decompositions for K_(1,g,g)(g-1)when g is even and for K^(1,g,1/2(g-1)2)when g is odd are obtained.Using a recursive construction,we also obtain the thickness for some complete tripartite graphs.The results here support the long-standing conjecture that the thickness of K_(m,n)is[mn/2(m+n-2)]for any positive integers m,n.
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Science and Research Project of the Education Department of Gansu Province (Grant No.0501-02)
文摘Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.
文摘An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and indegree respectively of x. Define aui： dui^＋ - dus^-, bvj = dvj^＋ - dvj^- and cwk = dwk^＋ - dwk^- as the imbalances of the vertices ui in U, vj in V and wk in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite graph. Keywords Digraph, imbalance, outdegree, indegree, oriented graph, oriented tripartite graph, arc
文摘Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.
基金supported by National Natural Science Foundation of China(72293561)Research Center for Interactive Technology Industry of Tsinghua University(RCITI2022T002).
文摘Preference prediction is the building block of personalized services,and its implementation at the group level helps enterprises identify their target customers effectively.Existing methods for preference prediction mainly focus on behavioral interactions to extract the associations between groups and products,ignoring the importance of other auxiliary records(e.g.,online reviews and social tags)in association detection.This paper proposes a novel method named GMAT for group preference prediction,aiming to collectively detect the sophisticated association patterns from user generated content(UGC)and behavioral interactions.In doing so,we construct a tripartite graph to collaborate these two types of data,and design a deep-learning algorithm with mutual attention module for generating the contextualized representations of groups and products.Extensive experiments on two real-world datasets show that GMAT is superior to other baselines in terms of group preference prediction.Additionally,GMAT is able to improve prediction accuracy compared with its different variants,further verifying the proposed method’s effectiveness on association pattern detection.
文摘In the densification of Device-to-Device(D2D)-enabled Social Internet of Things(SIoT)networks,improper allocation of resources can lead to high interference,increased signaling overhead,latency,and disruption of Channel State Information(CSI).In this paper,we formulate the problem of sum throughput maximization as a Mixed Integer Non-Linear Programming(MINLP)problem.The problem is solved in two stages:a tripartite graph-based resource allocation stage and a time-scale optimization stage.The proposed approach prioritizes maintaining Quality of Service(QoS)and resource allocation to minimize power consumption while maximizing sum throughput.Simulated results demonstrate the superiority of the proposed algorithm over standard benchmark schemes.Validation of the proposed algorithm using performance parameters such as sum throughput shows improvements ranging from 17%to 93%.Additionally,the average time to deliver resources to CSI users is minimized by 60.83%through optimal power usage.This approach ensures QoS requirements are met,reduces system signaling overhead,and significantly increases D2D sum throughput compared to the state-of-the-art schemes.The proposed methodology may be well-suited to address the challenges SIoT applications,such as home automation and higher education systems.
文摘Most entity ranking research aims to retrieve a ranked list of entities from a Web corpus given a user query. The rank order of entities is determined by the relevance between the query and contexts of entities. However, entities can be ranked directly based on their relative importance in a document collection, independent of any queries. In this paper, we introduce an entity ranking algorithm named NERank＋. Given a document collection, NERank＋ first constructs a graph model called Topical Tripartite Graph, consisting of document, topic and entity nodes. We design separate ranking functions to compute the prior ranks of entities and topics, respectively. A meta-path constrained random walk algorithm is proposed to propagate prior entity and topic ranks based on the graph model. We evaluate NERank＋ over real-life datasets and compare it with baselines. Experimental results illustrate the effectiveness of our approach.
